Jobs

Interviews

Discussions

Lowest Common Ancestor of a Binary Tree

Medium

Lowest Common Ancestor of a Binary Tree

Medium

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 binary tree be empty, or can p or q be null?
Are p and q guaranteed to exist in the tree?
Are the node values unique within the tree, or could there be duplicates?
Can a node be a descendant of itself, as the problem definition implies?
If p or q is the root, is the root still considered the lowest common ancestor?

Brute Force Solution

Approach

The brute force method for finding the lowest common ancestor in a family tree involves checking every possible ancestor. We explore all ancestor combinations for the two given individuals until we find the deepest one they share.

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

First, find all the ancestors of the first person.
Then, find all the ancestors of the second person.
Next, compare the two lists of ancestors to find the ones they have in common.
Finally, from all the common ancestors, choose the one that is the furthest down the family tree (the deepest). This is the lowest common ancestor.

Code Implementation

def lowest_common_ancestor_brute_force(root, node_one, node_two):
    def find_ancestors(node, target, ancestors_list):
        if not node:
            return False
        
        if node == target:
            ancestors_list.append(node)
            return True

        if find_ancestors(node.left, target, ancestors_list) or \
           find_ancestors(node.right, target, ancestors_list):
            ancestors_list.append(node)
            return True

        return False

    ancestors_node_one = []
    ancestors_node_two = []

    find_ancestors(root, node_one, ancestors_node_one)
    find_ancestors(root, node_two, ancestors_node_two)

    # Need to reverse to find from root to node
    ancestors_node_one.reverse()
    ancestors_node_two.reverse()

    lowest_common_ancestor = None

    # Find the common ancestors
    for i in range(min(len(ancestors_node_one), len(ancestors_node_two))):
        if ancestors_node_one[i] == ancestors_node_two[i]:
            lowest_common_ancestor = ancestors_node_one[i]
        else:
            break

    # Return the last common ancestor
    return lowest_common_ancestor

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – Finding all ancestors for each node in a binary tree of n nodes can take O(n) time in the worst case (e.g., skewed tree). Since we need to do this for both nodes, that's already O(n). Then, comparing the two lists of ancestors, each of which can be of size O(n), requires comparing each element in one list to each element in the other list, leading to O(n*n) operations. The final step of finding the deepest common ancestor among the common ancestors takes at most O(n) time. Thus the dominant factor is the comparison of the ancestor lists, leading to O(n²).

Space Complexity

O(N) – The space complexity is determined by the storage of ancestors for both input nodes. In the worst-case scenario, where the binary tree is skewed, the list of ancestors for each node could potentially contain all the nodes from the root to that node. This means we could store two lists, each potentially of size N, where N is the number of nodes in the tree. Therefore, the auxiliary space required to store these ancestor lists grows linearly with the number of nodes in the tree, resulting in a space complexity of O(N).

Optimal Solution

Approach

The most efficient way to find the lowest common ancestor is to use a method that explores the tree only as needed. We'll use recursion to search for the target nodes and simultaneously identify the common ancestor. The key idea is that if a node has both target nodes in its subtrees, it is the lowest common ancestor.

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

Start at the root of the tree.
For each node, check if it is one of the target nodes we're looking for. If it is, we remember that we've found one of the targets.
Recursively check the left side of the node to see if it contains either of the target nodes.
Recursively check the right side of the node to see if it contains either of the target nodes.
If both the left and right sides contain one of the target nodes, then the current node is the lowest common ancestor. We have found our answer!
If only one side contains target nodes, pass that side up the chain, meaning the ancestor lies on that side.
If neither side has target nodes, pass up the signal that no target node was found in this area.

Code Implementation

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

def lowestCommonAncestor(root, first_node, second_node):
    if not root:
        return None

    # If the current node is one of the target nodes.
    if root == first_node or root == second_node:
        return root

    left_subtree_result = lowestCommonAncestor(root.left, first_node, second_node)

    right_subtree_result = lowestCommonAncestor(root.right, first_node, second_node)

    #If both subtrees have a result, this node is the LCA
    if left_subtree_result and right_subtree_result:
        return root

    #If only one subtree has a result, return that result
    return left_subtree_result if left_subtree_result else right_subtree_result

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm traverses the binary tree in a depth-first manner. In the worst-case scenario, the algorithm visits every node in the tree to find the lowest common ancestor. The recursion explores each node to check if it or its descendants contain the target nodes, effectively visiting each node once. Therefore, the time complexity is directly proportional to the number of nodes, n, in the binary tree.

Space Complexity

O(H) – The space complexity is primarily determined by the recursion depth, where H is the height of the binary tree. In the worst-case scenario, such as a skewed tree, the recursion depth can be equal to N (the number of nodes), as each recursive call adds a new frame to the call stack until it reaches a leaf node. However, in a balanced tree, the height is logarithmic, resulting in a space complexity of O(log N). Therefore, the space complexity is O(H) reflecting the maximum depth of the recursion stack.

Edge Cases

Case	How to Handle
Root is null	Return null immediately, as an empty tree has no LCA.
p or q is null	Return null if either p or q is null, as LCA is not defined.
Tree has only one node (root)	Return the root if root is either p or q; otherwise return null.
p and q are the same node	Return p (or q) since a node is an ancestor of itself.
p is an ancestor of q	Return p since it is the lowest ancestor containing both.
q is an ancestor of p	Return q since it is the lowest ancestor containing both.
p or q is not in the tree	The standard recursive solution will still function correctly, ultimately returning null if only one or neither node is found by the search.
Skewed Tree (left or right)	The solution should still work correctly, though the recursive calls might take longer to complete in a highly skewed tree.

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 binary tree be empty, or can p or q be null?
Are p and q guaranteed to exist in the tree?
Are the node values unique within the tree, or could there be duplicates?
Can a node be a descendant of itself, as the problem definition implies?
If p or q is the root, is the root still considered the lowest common ancestor?

Brute Force Solution

Approach

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

First, find all the ancestors of the first person.
Then, find all the ancestors of the second person.
Next, compare the two lists of ancestors to find the ones they have in common.
Finally, from all the common ancestors, choose the one that is the furthest down the family tree (the deepest). This is the lowest common ancestor.

Code Implementation

def lowest_common_ancestor_brute_force(root, node_one, node_two):
    def find_ancestors(node, target, ancestors_list):
        if not node:
            return False
        
        if node == target:
            ancestors_list.append(node)
            return True

        if find_ancestors(node.left, target, ancestors_list) or \
           find_ancestors(node.right, target, ancestors_list):
            ancestors_list.append(node)
            return True

        return False

    ancestors_node_one = []
    ancestors_node_two = []

    find_ancestors(root, node_one, ancestors_node_one)
    find_ancestors(root, node_two, ancestors_node_two)

    # Need to reverse to find from root to node
    ancestors_node_one.reverse()
    ancestors_node_two.reverse()

    lowest_common_ancestor = None

    # Find the common ancestors
    for i in range(min(len(ancestors_node_one), len(ancestors_node_two))):
        if ancestors_node_one[i] == ancestors_node_two[i]:
            lowest_common_ancestor = ancestors_node_one[i]
        else:
            break

    # Return the last common ancestor
    return lowest_common_ancestor

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start at the root of the tree.
For each node, check if it is one of the target nodes we're looking for. If it is, we remember that we've found one of the targets.
Recursively check the left side of the node to see if it contains either of the target nodes.
Recursively check the right side of the node to see if it contains either of the target nodes.
If both the left and right sides contain one of the target nodes, then the current node is the lowest common ancestor. We have found our answer!
If only one side contains target nodes, pass that side up the chain, meaning the ancestor lies on that side.
If neither side has target nodes, pass up the signal that no target node was found in this area.

Code Implementation

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

def lowestCommonAncestor(root, first_node, second_node):
    if not root:
        return None

    # If the current node is one of the target nodes.
    if root == first_node or root == second_node:
        return root

    left_subtree_result = lowestCommonAncestor(root.left, first_node, second_node)

    right_subtree_result = lowestCommonAncestor(root.right, first_node, second_node)

    #If both subtrees have a result, this node is the LCA
    if left_subtree_result and right_subtree_result:
        return root

    #If only one subtree has a result, return that result
    return left_subtree_result if left_subtree_result else right_subtree_result

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Root is null	Return null immediately, as an empty tree has no LCA.
p or q is null	Return null if either p or q is null, as LCA is not defined.
Tree has only one node (root)	Return the root if root is either p or q; otherwise return null.
p and q are the same node	Return p (or q) since a node is an ancestor of itself.
p is an ancestor of q	Return p since it is the lowest ancestor containing both.
q is an ancestor of p	Return q since it is the lowest ancestor containing both.
p or q is not in the tree	The standard recursive solution will still function correctly, ultimately returning null if only one or neither node is found by the search.
Skewed Tree (left or right)	The solution should still work correctly, though the recursive calls might take longer to complete in a highly skewed tree.