Lowest Common Ancestor of a Binary Tree II

Medium

Asked by:

42 views

Topics:

TreesRecursion

Given the root of a binary tree, return the lowest common ancestor (LCA) of two given nodes, p and q, in the tree. If either node p or q does not exist in the tree, return null. All values of the nodes in the tree are unique.

According to the definition of LCA on binary tree:

The lowest common ancestor of two nodes p and q in a binary tree is the lowest node that has both p and q as descendants (where we allow a node to be a descendant of itself).

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 10
Output: null
Explanation: Node 10 does not exist in the tree, so return null.

Constraints:

The number of nodes in the tree is in the range [1, 10⁴].
-10⁹ <= Node.val <= 10⁹
All Node.val are unique.
p != q

Follow up: Can you find the LCA traversing the tree, without checking nodes?

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:

Can the values of the nodes in the tree be duplicated?
What should I return if either p or q is not present in the tree?
Is it guaranteed that both p and q are different nodes within the tree when they are present?
Can p or q ever be the root node?
Can I assume that p and q are valid `TreeNode` objects or do I need to handle the case where they are null?

Brute Force Solution

Approach

The brute force way to find the lowest common ancestor of two people in a family tree is to check every possibility. We can do this by looking at all the ancestors of each person. The first ancestor they share in common as we go up the tree is the lowest common ancestor.

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

First, list all the ancestors of the first person, going up the family tree until you reach the very top.
Next, list all the ancestors of the second person, doing the same thing.
Now, compare the two lists of ancestors, starting with the most recent ancestors (the parents).
Go through the lists until you find the first ancestor that appears in both lists. This common ancestor is the lowest one they share.
If you get to the top of both lists without finding a common ancestor, it means there is no common ancestor in the family tree.

Code Implementation

def lowest_common_ancestor_brute_force(root, node_one, node_two):
    def find_ancestors(node):
        ancestors = []
        current_node = node

        while current_node:
            ancestors.append(current_node)
            # Assuming each node has a 'parent' attribute.
            if not hasattr(current_node, 'parent'):
                return []
            current_node = current_node.parent
        return ancestors

    node_one_ancestors = find_ancestors(node_one)
    node_two_ancestors = find_ancestors(node_two)

    # Reverse the lists to start from the immediate parents.
    node_one_ancestors.reverse()
    node_two_ancestors.reverse()

    # Iterate to find the lowest common ancestor
    lowest_common_ancestor = None
    for i in range(min(len(node_one_ancestors), len(node_two_ancestors))):
        # Stop when there's a divergence in ancestors.
        if node_one_ancestors[i] == node_two_ancestors[i]:
            lowest_common_ancestor = node_one_ancestors[i]
        else:
            break

    # Return the found common ancestor.
    return lowest_common_ancestor

Big(O) Analysis

Time Complexity

O(n) – Let n be the number of nodes in the binary tree. The algorithm first finds all ancestors of node p, which in the worst case (a skewed tree) can be n. Similarly, finding all ancestors of node q can also take O(n) time. Comparing the two lists of ancestors, each of maximum size n, to find the first common element takes O(n) time. Therefore, the overall time complexity is O(n) + O(n) + O(n) which simplifies to O(n).

Space Complexity

O(N) – The algorithm creates two lists to store the ancestors of each node. In the worst-case scenario, both nodes are leaf nodes in a tree that resembles a linked list, requiring storage for all nodes from the root to each leaf. Therefore, each list could contain up to N elements, where N is the number of nodes in the tree. Thus, the auxiliary space is proportional to N, resulting in O(N) space complexity.

Optimal Solution

Approach

The most efficient way to find the lowest common ancestor (LCA) in a binary tree when we know two nodes exist involves a single tree traversal. The idea is to recursively search for the nodes and track when they are found, returning relevant information up the tree. If both nodes are found in a subtree, the root of that subtree is the LCA.

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

Start at the root of the tree.
Recursively explore the left side of the current node, searching for the two target nodes.
Recursively explore the right side of the current node, searching for the two target nodes.
If the current node is one of the target nodes OR if both target nodes were found within its left and right subtrees, then the current node is the lowest common ancestor.
If only one of the target nodes was found in either the left or right subtrees, return that found node to the parent node.
If neither target node was found in either subtree, return nothing to the parent node.
Continue this process upwards to the root, and the first node encountered where both target nodes are 'underneath' it (either directly or within its subtrees) is the LCA.

Code Implementation

def lowest_common_ancestor(root, first_node, second_node):
    def recurse_tree(node):
        if not node:
            return None

        # Recursively search the left subtree
        left_result = recurse_tree(node.left)

        # Recursively search the right subtree
        right_result = recurse_tree(node.right)

        # If the current node is one of the target nodes
        node_is_target = node == first_node or node == second_node

        # If the target nodes were found in left and right subtrees
        if left_result and right_result:
            return node

        # If the current node is a target node and either target was found in a subtree
        if node_is_target and (left_result or right_result):
            return node

        # If the current node is a target node
        if node_is_target:
            return node

        # Propagate results up the tree.
        return left_result or right_result

    return recurse_tree(root)

Big(O) Analysis

Time Complexity

O(n) – The provided solution performs a single traversal of the binary tree to find the lowest common ancestor (LCA). In the worst-case scenario, we visit each node of the tree once. The number of nodes in the tree is denoted by 'n', where 'n' represents the size of the input. Therefore, the time complexity is directly proportional to the number of nodes visited, leading to O(n) time complexity, as the algorithm examines each node at most once during the recursive traversal.

Space Complexity

O(H) – The space complexity is determined primarily by the recursion depth of the function calls. In the worst-case scenario, the binary tree might resemble a linked list, forcing the recursive calls to go as deep as the height (H) of the tree. Each recursive call adds a new frame to the call stack, which consumes memory. Therefore, the auxiliary space used corresponds to the maximum depth of the recursion, which is O(H), where H is the height of the binary tree. In a balanced tree, H would be log(N), but in a skewed tree, H could be N.

Edge Cases

Case	How to Handle
Root is null	Return null immediately since there is no tree to traverse.
p or q is null	Return null if either p or q are null as LCA cannot be defined.
p and q are the same node	Return p (or q) since the lowest common ancestor of a node with itself is the node itself.
Either p or q, or both, do not exist in the tree.	Return null if either p or q are not in the tree, which can be determined during the recursive traversal.
Large, unbalanced tree (e.g., skewed tree)	Recursive solution may lead to stack overflow; consider iterative solution using a parent pointer map.
Tree with a single node that is either p or q.	If the root is equal to either p or q, check if the other node is present in the tree; if not, return null, otherwise return the root.
p is an ancestor of q or q is an ancestor of p	The algorithm should correctly identify the ancestor as the LCA in these situations.
All node values are the same, potentially including p and q.	The algorithm relies on object identity (pointer comparison), not value comparison, so identical values should not affect correctness.

Root is null

How to Handle:

Return null immediately since there is no tree to traverse.

p or q is null

How to Handle:

Return null if either p or q are null as LCA cannot be defined.

p and q are the same node

How to Handle:

Return p (or q) since the lowest common ancestor of a node with itself is the node itself.

Either p or q, or both, do not exist in the tree.

How to Handle:

Return null if either p or q are not in the tree, which can be determined during the recursive traversal.

Large, unbalanced tree (e.g., skewed tree)

How to Handle:

Recursive solution may lead to stack overflow; consider iterative solution using a parent pointer map.

Tree with a single node that is either p or q.

How to Handle:

If the root is equal to either p or q, check if the other node is present in the tree; if not, return null, otherwise return the root.

p is an ancestor of q or q is an ancestor of p

How to Handle:

The algorithm should correctly identify the ancestor as the LCA in these situations.

All node values are the same, potentially including p and q.

How to Handle:

The algorithm relies on object identity (pointer comparison), not value comparison, so identical values should not affect correctness.