Command Palette

Search for a command to run...

Hectal
Problem 16.10 · Binary TreesMedium

Lowest Common Ancestor of a Binary Tree

PatternTree DFS

What it teaches: Post-order signals: each subtree reports whether it found p or q; the first node with reports from both sides is the LCA.

Practise it on judges as “Lowest Common Ancestor of a Binary Tree”.

The problem

Given a binary tree with distinct values and two values p and q that both exist in it, return the value of their lowest common ancestor: the deepest node that has both as descendants (a node counts as its own descendant).

Example 1

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3

Example 2

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5

Constraints

  • 2 ≤ nodes ≤ 10⁵
  • Distinct values; p and q exist

Pattern clues in the wording

  • → Information must come up from both subtrees

These clues point to Tree DFS: Recurse into the left and right children and combine what they return (height, sums, paths).

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public int lowestCommonAncestor(TreeNode root, int p, int q) {
        return root.val;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
root = [3,5,1,6,2,0,8,null,null,7,4]
p = 5
q = 1
3
2
root = [3,5,1,6,2,0,8,null,null,7,4]
p = 5
q = 4
5
3
root = [3,5,1,6,2,0,8,null,null,7,4]
p = 6
q = 4
5

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Post-order search · O(n)
1

Post-order search

Time O(n) Space O(h)

find(n): null → null; if n is p or q return n; l = find(left), r = find(right); if both non-null return n; else return the non-null one.

▶ Dry run: Where the reports meetroot = [3,5,1,6,2,0,8,null,null,7,4], p = 6, q = 4
657243018

Step 1/4Searching under 5: its left child 6 is p, so it reports 6.

Approach 1
class Solution {
    public int lowestCommonAncestor(TreeNode root, int p, int q) {
        return find(root, p, q).val;
    }

    private TreeNode find(TreeNode n, int p, int q) {
        if (n == null || n.val == p || n.val == q) return n;
        TreeNode l = find(n.left, p, q), r = find(n.right, p, q);
        if (l != null && r != null) return n;
        return l != null ? l : r;
    }
}

Verdict: One pass, no parent pointers.

Before you submit

Edge cases and common mistakes

Test these inputs

  • p is an ancestor of q
  • p and q in different subtrees of the root

Mistakes people make

  • Continuing to search below p after finding it (unnecessary: if q is below p, p is the LCA).

Interview

Follow-up questions

How does it change for a binary search tree?