Finding the Lowest Common Ancestor of Two Nodes in Any Binary Tree: From Recursion to Optimization

Introduction

Finding the Lowest Common Ancestor (LCA) of two nodes in a binary tree is a classic problem in data structures. Given any binary tree (not necessarily a binary search tree) and two nodes, the LCA is defined as the deepest node that is an ancestor of both. This problem has wide applications in compiler design, network routing, and bioinformatics. Based on high-quality discussions from Stack Overflow, this article systematically introduces multiple algorithms, with a focus on optimal solutions.

Naive Approach: Traversal-Based Algorithm

An intuitive method uses inorder and postorder traversals. For nodes p and q, first obtain the inorder traversal sequence and identify all nodes between p and q. Then, check these nodes in the postorder sequence; the last appearing node is the LCA. For example, in the referenced binary tree, the inorder nodes between 8 and 5 are [4,9,2], and the last in postorder is 2, so the LCA is 2.

This approach has a time complexity of O(n), where n is the number of nodes, due to two traversals and array iterations. However, it has significant drawbacks: it relies on traversal order, may fail for certain tree structures, and requires O(n) extra space for storing sequences. Thus, it is not a robust solution.

Recursive Algorithm: Standard Implementation

A more reliable method is recursive search. The core idea is to start from the root and recursively search for p and q in the left and right subtrees. If the current node is p or q, return it as a potential LCA. Otherwise, recursively find results in the left and right subtrees. If p and q are in different subtrees, the current node is the LCA; if they are in the same subtree, return that subtree's result.

Here is a C-style code implementation:

struct node* findLCA(struct node* root, struct node* p, struct node* q) {
    if (!root) return NULL;
    if (root == p || root == q) return root;
    
    struct node* left = findLCA(root->left, p, q);
    struct node* right = findLCA(root->right, p, q);
    
    if (left && right) return root;
    return left ? left : right;
}

This algorithm has a time complexity of O(n), as each node is visited at most once. Space complexity is O(h), where h is the tree height, determined by the recursion stack depth. It correctly handles cases where p or q is a direct child of the other, avoiding errors in earlier versions.

Optimized Algorithm: Leveraging Parent Pointers

When binary tree nodes include pointers to their parents, a more efficient algorithm can be designed. The basic steps are: first, traverse upward from node p to the root, recording the path. Do the same for node q. Then, compare the two paths to find the last common node, which is the LCA.

For example, for node 8, the path is {4, 2, 1} (assuming the root is 1). For node 5, the path is {2, 1}. Comparing paths, the last common node before the first difference is 2, so the LCA is 2.

This algorithm has a time complexity of O(h), where h is the tree height. In balanced trees, h = O(log n), offering better performance than the recursive approach. Space complexity is O(h) for storing paths. Further optimizations can achieve constant space by first computing node depths and then moving pointers upward synchronously.

Depth Synchronization Algorithm

If nodes have parent pointers, another method involves computing the depths of p and q first. Then, move the deeper node upward until both depths are equal. Next, move both nodes upward simultaneously until they meet; the meeting point is the LCA.

Pseudocode is as follows:

findLCA(v, w):
    depth_v = depth(v)
    depth_w = depth(w)
    while depth_v != depth_w:
        if depth_v > depth_w:
            v = parent(v)
            depth_v--
        else:
            w = parent(w)
            depth_w--
    while v != w:
        v = parent(v)
        w = parent(w)
    return v

Depth computation can be done by traversing upward to the root in O(h) time. Overall, the algorithm has O(h) time complexity and O(1) space complexity. This is suitable for deep trees, avoiding recursion stack overflow risks.

Advanced Techniques: Preprocessing for Constant-Time Queries

For scenarios requiring multiple LCA queries, preprocessing techniques can be employed. For instance, using Euler tours and Range Minimum Query (RMQ), the tree can be preprocessed in O(n) time, enabling O(1) query time thereafter. This method is particularly effective for static trees (no structural modifications) but involves complex implementations with additional data structures.

Conclusion

This article systematically presents multiple solutions for the LCA problem in binary trees. The recursive algorithm is general and simple, with O(n) time complexity, suitable for trees without parent pointers. When parent pointers are available, optimized algorithms reduce time complexity to O(h), significantly improving performance. The depth synchronization algorithm further optimizes space usage. In practice, the choice of algorithm should depend on tree structure and query requirements. For frequent queries, preprocessing methods can be considered to achieve constant query time. These algorithms exemplify the trade-offs between time and space in computer science, serving as classic case studies in algorithm design.