To solve the “Lowest Common Ancestor in Binary Tree” problem, we can use a recursive approach. The idea is to traverse the tree starting from the root and recursively search for the lowest common ancestor in the left and right subtrees. The base cases for the recursion are:

  1. If the current node is None, return None.
  2. If the current node is either p or q, return the current node.
  3. If both left and right subtrees return non-None values, it means that p and q are found in separate subtrees, and the current node is the lowest common ancestor.
  4. If only one subtree returns a non-None value, it means that both p and q are in that subtree, and the non-None value is the lowest common ancestor.

Here’s the 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(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    # Base cases
    if not root:
        return None

    if root == p or root == q:
        return root

    # Recursively search in left and right subtrees
    left_lca = lowest_common_ancestor(root.left, p, q)
    right_lca = lowest_common_ancestor(root.right, p, q)

    # If both left and right subtrees return non-None values, current node is the LCA
    if left_lca and right_lca:
        return root

    # If only one subtree returns non-None value, that is the LCA
    return left_lca or right_lca

# Example usage:
root = TreeNode(3,
                TreeNode(5, 
                         TreeNode(6), 
                         TreeNode(2, 
                                  TreeNode(7), 
                                  TreeNode(4)
                                  )
                         ),
                TreeNode(1, 
                         TreeNode(0), 
                         TreeNode(8)
                         )
                )

result1 = lowest_common_ancestor(root, root.left, root.right)  
print(result1.val)
assert result1.val == 3

result2 = lowest_common_ancestor(root, root.left, root.left.right.right)  
assert result2.val == 5
print(result2.val)

result3 = lowest_common_ancestor(root, root.left, root.right.left)  
assert result3.val == 3
print(result3.val)

Time Complexity:

The time complexity is ON), where N is the number of nodes in the binary tree. We visit each node once during the recursive traversal.

Space Complexity:

The space complexity is O(H), where H is the height of the binary tree. This is the maximum depth of the recursive call stack. In the worst case, the depth of the recursion is equal to the height of the tree.