Lowest Common Ancestor of a Binary Tree IV

Medium

Atlassian

8 views

Topics:

TreesRecursion

Given the root of a binary tree where each node has a unique value, and an array of n node values nodes, return the lowest common ancestor (LCA) of all nodes in nodes. All the nodes will exist in the tree, and all node values will be unique.

Extending the definition of LCA on Wikipedia: “The lowest common ancestor of two nodes v and w in a tree T is the lowest node that has both v and w as descendants (where we allow a node to be a descendant of itself).”

A descendant of a node x is any node from the subtree rooted at x.

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], nodes = [4,7]
Output: 2
Explanation: The lowest common ancestor of nodes 4 and 7 is node 2.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], nodes = [4,6,7]
Output: 5
Explanation: The lowest common ancestor of nodes 4, 6, and 7 is node 5.

Example 3:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], nodes = [5]
Output: 5
Explanation: The lowest common ancestor of a single node is the node itself.

Constraints:

The number of nodes in the tree is in the range [1, 10⁴].
-10⁹ <= Node.val <= 10⁹
All Node.val are unique.
1 <= nodes.length <= 10⁴
nodes.length <= n, where n is the number of nodes in the tree.
All the nodes in nodes exist in the tree.

Try coding it in LeetCode

Lowest Common Ancestor of a Binary Tree IV

Medium

Atlassian

8 views

Topics:

TreesRecursion

Given the root of a binary tree where each node has a unique value, and an array of n node values nodes, return the lowest common ancestor (LCA) of all nodes in nodes. All the nodes will exist in the tree, and all node values will be unique.

Extending the definition of LCA on Wikipedia: “The lowest common ancestor of two nodes v and w in a tree T is the lowest node that has both v and w as descendants (where we allow a node to be a descendant of itself).”

A descendant of a node x is any node from the subtree rooted at x.

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], nodes = [4,7]
Output: 2
Explanation: The lowest common ancestor of nodes 4 and 7 is node 2.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], nodes = [4,6,7]
Output: 5
Explanation: The lowest common ancestor of nodes 4, 6, and 7 is node 5.

Example 3:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], nodes = [5]
Output: 5
Explanation: The lowest common ancestor of a single node is the node itself.

Constraints:

The number of nodes in the tree is in the range [1, 10⁴].
-10⁹ <= Node.val <= 10⁹
All Node.val are unique.
1 <= nodes.length <= 10⁴
nodes.length <= n, where n is the number of nodes in the tree.
All the nodes in nodes exist in the tree.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Is it guaranteed that all nodes in the `nodes` array are present in the tree rooted at `root`?
Can the `nodes` array be empty or contain only the root node?
If the `nodes` array contains only one node, should I return that node as the LCA?
Are the values of the nodes in the tree unique, or can there be duplicate values?
If the lowest common ancestor of the nodes is the root itself, should I return the root?

Brute Force Solution

Approach

The problem asks us to find the shared parent node that is deepest in the tree for a given set of nodes. The brute force method essentially checks every node to see if it can be the lowest common ancestor, by verifying if all the target nodes are descendants of it.

Here's how the algorithm would work step-by-step:

Look at each node in the tree, one by one.
For each node, check if all the special target nodes are located somewhere under that node in the tree (meaning they are descendants).
If all the target nodes are descendants of the current node, then this current node is a potential common ancestor.
Among all the potential common ancestors we found, choose the one that is located deepest in the tree (furthest from the root). This is the lowest common ancestor.
If no node is found to be a common ancestor, it means the provided target nodes are not present in the tree, or are not located under a common parent.

Code Implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def lowest_common_ancestor_brute_force(root, nodes):
    potential_lcas = None

    def is_descendant(node, target_node):
        if not node:
            return False
        if node == target_node:
            return True
        return is_descendant(node.left, target_node) or is_descendant(node.right, target_node)

    def all_nodes_are_descendants(current_node, target_nodes):
        for target_node in target_nodes:
            if not is_descendant(current_node, target_node):
                return False
        return True

    def find_all_nodes(node):
        if not node:
            return []
        return [node] + find_all_nodes(node.left) + find_all_nodes(node.right)

    all_tree_nodes = find_all_nodes(root)

    for current_node in all_tree_nodes:
        # Check if the current node is a potential LCA.
        if all_nodes_are_descendants(current_node, nodes):

            # Update potential_lcas if current node is deeper.
            if not potential_lcas:
                potential_lcas = current_node
            else:
                def get_depth(node):
                    if not node:
                        return 0
                    return 1 + max(get_depth(node.left), get_depth(node.right))

                current_depth = get_depth(current_node)
                existing_depth = get_depth(potential_lcas)

                if current_depth > existing_depth:
                    potential_lcas = current_node

    # Return the deepest common ancestor found
    return potential_lcas

Big(O) Analysis

Time Complexity

O(n*m) – The algorithm iterates through each node in the binary tree, which takes O(n) time, where n is the number of nodes in the tree. For each node, we check if all m target nodes are descendants of it. The descendant check for each target node can take O(h) time in the worst case, where h is the height of the tree. In the worst case, the height of the tree can be n, so the descendant check can take O(n) time. Therefore, the overall time complexity is O(n*m), because for each of the n nodes, we perform the descendant check for all m target nodes, each potentially taking O(n) time in the worst case (height of the tree is n).

Space Complexity

O(N) – The brute force approach, as described, implicitly uses recursion to traverse the binary tree to check if the target nodes are descendants of each potential common ancestor. In the worst-case scenario, the recursion stack can grow up to the height of the tree. For a skewed tree, the height can be equal to N, where N is the number of nodes in the tree. Therefore, the auxiliary space complexity is O(N) due to the recursion stack.

Optimal Solution

Approach

The key idea is to traverse the tree recursively. As we explore the tree, we check if the current node is one of the target nodes we are looking for. If it is, we know that node is an ancestor.

Here's how the algorithm would work step-by-step:

Start at the root of the tree.
Go down each branch (left and right) and check if either branch returns a node.
If a branch returns a node, it means it found at least one of the target nodes in that subtree.
If both branches return a node, it means that the current node is the lowest common ancestor because it's the first node that has target nodes in both its left and right subtrees. Return the current node.
If only one branch returns a node, return that node up the tree, signaling that a target node was found somewhere below.
If neither branch returns a node, check if the current node is one of the target nodes. If it is, return the current node.
If the current node is not a target node and neither branch found a target node, return nothing (representing no target nodes found in this subtree).

Code Implementation

def lowestCommonAncestor(root, nodes):
    def recurse_tree(current_node):
        if not current_node:
            return None

        # Recursively search in the left subtree
        left_subtree = recurse_tree(current_node.left)

        # Recursively search in the right subtree
        right_subtree = recurse_tree(current_node.right)

        # If both subtrees return a node, current node is LCA
        if left_subtree and right_subtree:
            return current_node

        # If either subtree returns a node, return that node
        if left_subtree:
            return left_subtree
        if right_subtree:
            return right_subtree

        # Check if the current node is one of the target nodes
        if current_node in nodes:
        # The node is one of the target nodes
            return current_node

        return None

    return recurse_tree(root)

Big(O) Analysis

Time Complexity

O(n) – The algorithm performs a depth-first traversal of the binary tree, where n represents the number of nodes in the tree. In the worst-case scenario, the function visits each node of the tree once to determine if it's a target node or to explore its subtrees. Therefore, the time complexity is directly proportional to the number of nodes in the tree. Even with multiple target nodes, each node is visited at most once during the recursive traversal, thus maintaining the linear time complexity.

Space Complexity

O(H) – The space complexity is determined primarily by the recursive call stack. In the worst-case scenario, where the tree is skewed (essentially a linked list), the recursion might go as deep as the height (H) of the tree, with each recursive call adding a new frame to the stack. Thus, the auxiliary space used by the call stack is proportional to the height of the tree, H. In the best or average case for a balanced tree, H would be log(N) where N is the number of nodes, but in the worst case it will be N. Therefore we denote the space complexity as O(H).

Edge Cases

Case	How to Handle
root is null	Return null if the root is null, as there is no tree to traverse.
nodes array is null or empty	Return null if the nodes array is empty because there's nothing to find the LCA for.
nodes array contains null node(s)	Handle null nodes in the input array by skipping them during LCA calculation, or throw an exception, depending on requirements.
All nodes in 'nodes' are the same node (e.g., the root)	The LCA should be that single node, so ensure the algorithm correctly identifies it.
One of the nodes in 'nodes' is the root, and all other nodes are descendants of that root	The LCA should be the root node itself.
None of the nodes in 'nodes' are present in the tree	Return null, indicating that no common ancestor exists for the given nodes in the tree.
The tree is highly skewed (e.g., a linked list)	The recursive calls could potentially lead to stack overflow for very deep trees, so iterative solutions should be considered for better performance and memory usage.
The tree is large and 'nodes' contains a significant number of nodes scattered throughout the tree	Ensure the solution scales efficiently, potentially using memoization or other optimization techniques to avoid redundant calculations.