Lowest Common Ancestor

The Lowest Common Ancestor (LCA) of two nodes p and q is the deepest node that has both p and q as descendants (a node can be a descendant of itself).

Node Definition

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}

Visual Example

        3
       / \
      5   1
     / \\ / \
    6  2 0  8
      / \
     7   4

• LCA(5, 1) = 3
• LCA(5, 4) = 5 (node is ancestor of itself)
• LCA(6, 4) = 5
• LCA(7, 4) = 2

LCA for Binary Trees - DFS Approach

Key insight: If current node is null, p, or q, return it. Otherwise recurse left and right. If both sides return non-null, current is LCA. If one side is null, return the other.

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;

    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);

    if (left != null && right != null) return root;
    return left != null ? left : right;
}

Why this works:

1. If p and q are in different subtrees, the current node is their LCA
2. If one node is ancestor of the other, the ancestor is returned first
3. If neither exists in a subtree, null propagates up

LCA for BST - Exploit BST Property

Since BST is ordered, we can determine which subtree to search:

public TreeNode lcaBST(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) return null;

    if (p.val < root.val && q.val < root.val) {
        return lcaBST(root.left, p, q);  // Both in left
    }
    if (p.val > root.val && q.val > root.val) {
        return lcaBST(root.right, p, q);  // Both in right
    }
    return root;  // Split point = LCA
}

LCA with Parent Pointers

Given each node has a parent pointer, find LCA by moving both to same depth, then moving up together:

public TreeNode lcaWithParent(TreeNode p, TreeNode q) {
    int depthP = getDepth(p);
    int depthQ = getDepth(q);

    // Move deeper node up
    while (depthP > depthQ) { p = p.parent; depthP--; }
    while (depthQ > depthP) { q = q.parent; depthQ--; }

    // Move both up until they meet
    while (p != q) {
        p = p.parent;
        q = q.parent;
    }
    return p;
}

private int getDepth(TreeNode node) {
    int depth = 0;
    while (node != null) {
        node = node.parent;
        depth++;
    }
    return depth;
}

Complexity Analysis

Approach	Time	Space
Binary Tree DFS	O(n)	O(h)
BST	O(h)	O(h)
Parent Pointers	O(h)	O(1)

where h is tree height (log n for balanced, n for skewed)

LCA of Multiple Nodes

Generalize to find LCA of a list of nodes:

public TreeNode lcaMultiple(TreeNode root, List<TreeNode> nodes) {
    Set<TreeNode> nodeSet = new HashSet<>(nodes);
    return helper(root, nodeSet);
}

private TreeNode helper(TreeNode root, Set<TreeNode> nodes) {
    if (root == null) return null;
    if (nodes.contains(root)) return root;

    TreeNode left = helper(root.left, nodes);
    TreeNode right = helper(root.right, nodes);

    if (left != null && right != null) return root;
    return left != null ? left : right;
}

Distance Between Two Nodes

Distance = depth(p) + depth(q) - 2 * depth(LCA)

public int findDistance(TreeNode root, TreeNode p, TreeNode q) {
    TreeNode lca = lowestCommonAncestor(root, p, q);
    return findDepth(lca, p, 0) + findDepth(lca, q, 0);
}

private int findDepth(TreeNode root, TreeNode target, int depth) {
    if (root == null) return -1;
    if (root == target) return depth;
    int left = findDepth(root.left, target, depth + 1);
    if (left != -1) return left;
    return findDepth(root.right, target, depth + 1);
}

Path Between Two Nodes

LCA helps find path: path(p, q) = path(root, p) + path(root, q) - 2 * path(root, LCA)

public List<TreeNode> findPath(TreeNode root, TreeNode target) {
    List<TreeNode> path = new ArrayList<>();
    findPathHelper(root, target, path);
    return path;
}

private boolean findPathHelper(TreeNode root, TreeNode target, List<TreeNode> path) {
    if (root == null) return false;
    path.add(root);
    if (root == target) return true;
    if (findPathHelper(root.left, target, path) || findPathHelper(root.right, target, path)) {
        return true;
    }
    path.remove(path.size() - 1);  // Backtrack
    return false;
}

Binary Tree Diameter

Diameter = longest path between any two nodes. Uses LCA concept:

private int diameter = 0;

public int diameterOfBinaryTree(TreeNode root) {
    height(root);
    return diameter;
}

private int height(TreeNode node) {
    if (node == null) return 0;
    int left = height(node.left);
    int right = height(node.right);
    diameter = Math.max(diameter, left + right);
    return 1 + Math.max(left, right);
}

Key Pattern

The LCA pattern applies whenever you need to find the "meeting point" of two paths in a tree. This includes:

• Distance between nodes
• Path between nodes
• Merging information from two subtrees
• Any problem asking about relationships between two nodes