Lowest Common Ancestor in a Binary Tree

Problem Description

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

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

Naive Approach

A brute-force approach would involve traversing the tree to find the paths from the root to both nodes p and q. Once we have these paths, we can compare them from the beginning until they diverge. The last common node in both paths is the LCA.

Algorithm:

1. Find the path from the root to node p. This can be done using Depth-First Search (DFS).
2. Find the path from the root to node q using DFS.
3. Compare the two paths element by element until you find the last matching node. This will be the LCA.

Code (Python):

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

def find_path(root, target, path):
    if root is None:
        return False
    
    path.append(root)
    
    if root == target:
        return True
    
    if (root.left and find_path(root.left, target, path)) or \
       (root.right and find_path(root.right, target, path)):
        return True
    
    path.pop()
    return False


def lowest_common_ancestor_naive(root, p, q):
    path_p = []
    path_q = []
    
    find_path(root, p, path_p)
    find_path(root, q, path_q)
    
lca = None
    for i in range(min(len(path_p), len(path_q))):
        if path_p[i] == path_q[i]:
            lca = path_p[i]
        else:
            break
    
    return lca

Time Complexity: O(N) in the worst case, where N is the number of nodes in the tree, because we might have to traverse the entire tree to find the paths to p and q.

Space Complexity: O(N) in the worst case, because the paths path_p and path_q can be as long as the height of the tree, which can be N in a skewed tree.

Optimal Approach (Recursive)

A more efficient approach uses recursion. The basic idea is as follows:

1. If the current node is None, return None.
2. If the current node is either p or q, return the current node.
3. Recursively search for p and q in the left and right subtrees.
4. If both left and right subtrees return a non-None node, then the current node is the LCA.
5. If only one subtree returns a non-None node, then that node is the LCA.

Code (Python):

def lowest_common_ancestor(root, p, q):
    if not root:
        return None
    
    if root == p or root == q:
        return root
    
    left_lca = lowest_common_ancestor(root.left, p, q)
    right_lca = lowest_common_ancestor(root.right, p, q)
    
    if left_lca and right_lca:
        return root
    elif left_lca:
        return left_lca
    else:
        return right_lca

Time Complexity: O(N), where N is the number of nodes in the tree. In the worst case, we visit each node once.

Space Complexity: O(H), where H is the height of the tree, due to the recursive call stack. In the worst case, H can be N (for a skewed tree), and in the best case, H can be log N (for a balanced tree).

Edge Cases

• Empty Tree: If the tree is empty (root is None), the function should return None.
• p or q is root: If either p or q is the root, the root is the LCA.
• p or q not in tree: The problem states that p and q will exist in the tree, so we don't need to explicitly handle this edge case.
• One node is the ancestor of the other: In this case, the ancestor node is the LCA.