Lesson 6 · Advanced structures and algorithms

Lowest Common Ancestor

The Lowest Common Ancestor (LCA) problem seeks the shared root of the smallest subtree containing two target nodes, utilizing recursive backtracking.

The LCA Concept

Given a tree and two nodes P and Q, the Lowest Common Ancestor is the deepest node in the tree that has both P and Q as descendants. It represents the point where the paths from the root to P and Q diverge.

Recursive Search

In a standard binary tree, LCA can be found via post-order traversal. A node asks its left and right children if they contain P or Q. If the current node receives a 'yes' from both children, or if the current node is P/Q and receives a 'yes' from one child, it is the LCA.

Key reference

Terms, operations, and practical uses

Core Concepts

AncestorAny node on the direct path from the root to the target node, including the target node itself.
Common AncestorA node that serves as an ancestor for both target node P and target node Q.
Lowest Common AncestorThe deepest possible common ancestor; the exact point where the paths to P and Q diverge.

Standard Binary Tree

Post-order ApproachRecursively search left and right. If both return a non-null target, the current node is the LCA.
Single Target ReturnIf only one side finds a target, pass that target up to the parent. It assumes both P and Q exist in the tree.
Path RecordingAn alternative O(N) space method is to record the path from root to P and root to Q, then find the last matching node.

Optimizations

BST LCAIn a BST, traverse down from root; the first node with a value strictly between P and Q is definitively the LCA.
Parent PointersIf nodes have parent references, track the path from P to root using a hash set, then traverse up from Q until a match is found.
Binary LiftingPrecomputing a jump table in O(N log N) to answer millions of LCA queries on a static tree in O(log N) time per query.

Code example

Find the lowest common ancestor

def lca(root, p, q):
    if not root or root == p or root == q:
        return root
    left = lca(root.left, p, q)
    right = lca(root.right, p, q)
    if left and right:
        return root
    return left if left else right
class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

left, right = TreeNode(2), TreeNode(3)
root = TreeNode(1, left, right)
print('LCA is', 'Root' if lca(root, left, right) is root else 'elsewhere')

TreeNode* lca(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
    TreeNode* left = lca(root->left, p, q);
    TreeNode* right = lca(root->right, p, q);
    if (left && right) return root;
    return left ? left : right;
}

TreeNode lca(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    TreeNode left = lca(root.left, p, q);
    TreeNode right = lca(root.right, p, q);
    if (left != null && right != null) return root;
    return left != null ? left : right;
}

Inputfind the common ancestor of the two displayed nodes

OutputLCA is Root

Example

Run the example step by step

Output

BST Optimization

If the tree is a Binary Search Tree, the LCA can be found iteratively in O(height) time without exploring the whole tree. We simply traverse down; the first node whose value lies strictly between the values of P and Q is guaranteed to be their LCA.

Binary Lifting

For applications where LCA is queried thousands of times on a static tree (like routing protocols), we can precompute a 'binary lifting' table in O(N log N) time. This table allows us to jump up the tree in powers of two, answering LCA queries in O(log N) time.