CodeWithYash

Intermediate · Module 13 · Lesson 7

Path & ancestor patterns

LCA, diameter, path sums, and subtree results.

15–25 min readLesson 76 of 123

Lesson 76 of 123

1d streak

Lowest Common Ancestor (LCA) & Path Invariants

The Lowest Common Ancestor (LCA) of two nodes p and q is the deepest node in the tree that has both p and q as descendants. In a BST, LCA can be found in $O(log n)$ time by comparing values against the root; in a general binary tree, postorder recursion finds it in $O(n)$ time.

LowestCommonAncestor.java
// 1. LCA in a Binary Search Tree: O(log n) time, O(1) space
public TreeNode lowestCommonAncestorBST(TreeNode root, TreeNode p, TreeNode q) {
    while (root != null) {
        if (p.val < root.val && q.val < root.val) {
            root = root.left; // Both nodes in left subtree
        } else if (p.val > root.val && q.val > root.val) {
            root = root.right; // Both nodes in right subtree
        } else {
            // Split point! One node is left, one is right (or root is p or q)
            return root;
        }
    }
    return null;
}

// 2. LCA in a General Binary Tree: O(n) time, O(h) space
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; // p and q found in separate subtrees!
    return left != null ? left : right;
}

Cost Model

Complexity & Trade-offs

Postorder traversal
O(n)
O(h)
The bound follows from the number of states visited and the work performed per transition.

When to use it

  • Hierarchies, ordered sets/maps, expression trees, and recursive aggregation.
  • Path, ancestor, depth, and subtree questions.
  • Maintaining sorted dynamic data with balanced trees.

Common mistakes

  • Assuming a BST is balanced without a balancing guarantee.
  • Confusing node depth with subtree height.
  • Discarding information needed by the parent instead of returning it.

Practice prompts

  • Reproduce the worked Path & ancestor patterns example without looking at the trace.
  • Change one input condition and explain whether the Path & ancestor patterns invariant still holds.
  • Implement the approach, derive its cost, and compare it with a straightforward baseline.

Mastery check

Can you derive it instead of memorizing it?

State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.