Command Palette

Search for a command to run...

Hectal
Problem 17.5 · Binary Search TreesMedium

Lowest Common Ancestor of a BST

PatternBST Ordering

What it teaches: The ordering tells you where the split happens without searching subtrees.

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

The problem

Given a BST and two values p and q present in it, return the value of their lowest common ancestor.

Example 1

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

Example 2

Input: same tree, p = 2, q = 4
Output: 2

Constraints

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

Pattern clues in the wording

  • → LCA on a BST

These clues point to BST Ordering: Use left < node < right to skip half the tree, and in-order traversal to visit values in sorted order.

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 = [6,2,8,0,4,7,9,null,null,3,5]
p = 2
q = 8
6
2
root = [6,2,8,0,4,7,9,null,null,3,5]
p = 2
q = 4
2

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Walk down until they split · O(h)
1

Walk down until they split

Time O(h) Space O(1)

Loop: both smaller → go left; both larger → go right; otherwise return the node.

▶ Dry run: p = 3, q = 5root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5]
023456789

Step 1/33 and 5 are both < 6: go left.

Approach 1
class Solution {
    public int lowestCommonAncestor(TreeNode root, int p, int q) {
        TreeNode cur = root;
        while (true) {
            if (p < cur.val && q < cur.val) cur = cur.left;
            else if (p > cur.val && q > cur.val) cur = cur.right;
            else return cur.val;
        }
    }
}

Verdict: No recursion, no full search.

Before you submit

Edge cases and common mistakes

Test these inputs

  • One value is the ancestor of the other
  • p > q

Mistakes people make

  • Using the general binary-tree LCA (correct but O(n)).

Interview

Follow-up questions

What if p or q may be missing?