Loading…

mediumTreesLC #235Frequently asked

Lowest Common Ancestor of a BST

Q: How do you solve Lowest Common Ancestor of a BST using the Generic Tree LCA — Recurse Both Subtrees approach?

When to use it: Mention it as the fallback that works on any binary tree, then point out it ignores the BST ordering and is therefore slower than necessary. This is the universal LCA algorithm — it works on *any* binary tree, ordered or not. It searches the tree bottom-up and lets each node report whether `p` or `q` was found beneath it. **The reporting contract.** Each recursive call returns a non-null node if it found `p`, `q`, or an LCA somewhere below. At a node, we recurse left and right. If *both* sides return non-null, then `p` and `q` were found on opposite sides, so the current node is their lowest common ancestor. If only one side returns non-null, we pass that result upward — the LCA (or the only target seen so far) lives on that side. **Why it's wasteful on a BST.** Nothing here uses the fact that left < node < right. We blindly explore both children of every node we touch, so in the worst case the whole tree is visited. On a *sorted* tree we can do far better by using a single comparison to discard an entire subtree at each step. **Why mention it anyway.** It's the correct answer to the sibling problem (LeetCode 236, plain binary tree), and saying 'here's the general method, but the BST lets me prune' demonstrates you understand exactly which property you're exploiting. Time complexity: O(n). Space complexity: O(h).

Q: How do you solve Lowest Common Ancestor of a BST using the BST Descent — Walk to the Split Point (Optimal) approach?

When to use it: The answer they want for a BST. Frame it as 'use the ordering to pick a direction, stop at the split'. On a BST we never need to look at both children. The ordering tells us which single direction can contain both targets, so we descend a single root-to-node path until the targets diverge. **The split-point insight.** Pick any node on the path from the root. If `p` and `q` are *both* greater than it, both live in its right subtree, so the LCA must be further right. If both are *smaller*, both live left. The only remaining case is that one target is ≤ node ≤ the other (or one of them equals the node). At that node, the paths to `p` and `q` go down different children — this is the lowest node that still has both as descendants, i.e. the LCA. We can stop the instant we reach it. **Why this is O(h), not O(n).** Each comparison lets us discard an entire subtree, so we touch one node per level and never branch. That collapses the search from 'visit everything' to 'follow one path', exactly like an ordinary BST search for a value. **Why iterative beats recursive here.** The recursion is tail-recursive — the recursive call is the last thing each frame does — so it carries no useful stack information. Rewriting it as a `while` loop reuses a single pointer variable and brings space down from O(h) to O(1). State that trade explicitly; it's the kind of detail interviewers reward. **Why we never run off the tree.** The problem guarantees both `p` and `q` exist, so a split point always lies on the shared prefix of their two root-paths. We are guaranteed to return before `node` becomes null. Time complexity: O(h). Space complexity: O(1).

LCPractice

Trees & BST · 8 of 41 · 8 min

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes p and q in the BST.

The lowest common ancestor is defined between two nodes p and q as the lowest node in the tree that has both p and q as descendants (where we allow **a node to be a descendant of itself**).

Both p and q exist in the BST and all node values are unique.

In plain English

We're walking down a sorted tree looking for the point where the paths to `p` and `q` part ways. Because every node's left subtree holds smaller values and its right subtree holds larger ones, comparing values tells us which way each target lies. A node is the LCA exactly when `p` and `q` are no longer on the same side of it.

Examples

Example 1

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Note: 2 is in the left subtree of 6 and 8 is in the right subtree, so they split at the root — 6 is the LCA.

Example 2

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Note: 4 lives in the subtree rooted at 2, so 2 is an ancestor of itself and of 4 — the LCA is 2.

Example 3

Input: root = [2,1], p = 2, q = 1
Output: 2
Note: 1 is the left child of 2; 2 is its own ancestor, so the LCA is 2.

Constraints

The number of nodes is in the range [2, 10⁵]
-10⁹ ≤ Node.val ≤ 10⁹
All Node.val are unique
p ≠ q, and both p and q exist in the BST

Clarifying questions4First question: Is the tree guaranteed to be a valid BST?Explore questions

Q1.Is the tree guaranteed to be a valid BST?
Yes — that's the whole point. The ordering invariant is what lets us pick a direction by comparing values instead of searching both subtrees.
Q2.Are p and q guaranteed to be present in the tree?
Yes. Because both exist, the descent always reaches a valid split point — we never need to verify existence separately.
Q3.Can a node be an ancestor of itself?
Yes. If p is an ancestor of q (or p == the split node), then p itself is the LCA. The 'else' branch covers node == p or node == q.
Q4.Are the values unique?
Yes, so comparing `p.val`/`q.val` against `node.val` is unambiguous — there's never a tie to break.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Exploit the BST ordering: start at the root and walk down. If both `p` and `q` are greater than the current node, the LCA is in the right subtree; if both are smaller, go left; the moment they split (one on each side, or one equals the current node) the current node IS the lowest common ancestor. O(h) time, O(1) space iteratively — no need for the generic O(n) tree-LCA search.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognize that the BST invariant lets you prune to a single root-to-node path instead of searching the whole tree — and whether you can express the descent in O(1) space.

Where candidates slip

Writing the generic O(n) binary-tree LCA (recursing both subtrees) and ignoring the BST ordering entirely, or getting the comparison directions backwards so you walk away from the answer.

How to stand out

Name the split-point insight out loud, do it iteratively in O(1) space, and contrast it with the LeetCode 236 plain-tree version to show you know exactly which property you're exploiting.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Generic Tree LCA — Recurse Both Subtrees	`O(n)`	`O(h)`	Mention it as the fallback that works on any binary tree, then point out it ignores the BST ordering and is therefore slower than necessary.	Read
2	BST Descent — Walk to the Split Point (Optimal)Optimal	`O(h)`	`O(1)`	The answer they want for a BST. Frame it as 'use the ordering to pick a direction, stop at the split'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewFind LCA of p and qIs it a BST (values ordered)?YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Generic Tree LCA — Recurse Both Subtrees

TimeO(n)SpaceO(h)

Mention it as the fallback that works on any binary tree, then point out it ignores the BST ordering and is therefore slower than necessary.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Forget the ordering for a second: on a plain binary tree, how would you know whether a subtree contains p, q, or both?

2Hint 2Explore hint

Recurse into left and right. If p and q come back from different sides, the current node is the LCA.

3Hint 3Explore hint

If both come back from the same side, the LCA is deeper on that side; if neither side has them, return null up the chain.

A · Core idea

This is the universal LCA algorithm — it works on any binary tree, ordered or not. It searches the tree bottom-up and lets each node report whether p or q was found beneath it.

The reporting contract. Each recursive call returns a non-null node if it found p, q, or an LCA somewhere below. At a node, we recurse left and right. If both sides return non-null, then p and q were found on opposite sides, so the current node is their lowest common ancestor. If only one side returns non-null, we pass that result upward — the LCA (or the only target seen so far) lives on that side.

Why it's wasteful on a BST. Nothing here uses the fact that left < node < right. We blindly explore both children of every node we touch, so in the worst case the whole tree is visited. On a sorted tree we can do far better by using a single comparison to discard an entire subtree at each step.

Why mention it anyway. It's the correct answer to the sibling problem (LeetCode 236, plain binary tree), and saying 'here's the general method, but the BST lets me prune' demonstrates you understand exactly which property you're exploiting.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

root = [6,2,8,0,4,7,9], p = 2, q = 8

node 6

recurse left (subtree of 2) and right (subtree of 8)

Statewaiting on both children

Final result6

C · Code with teaching comments

Reference implementation preview// Definition for a binary tree node. // class TreeNode { // int val; // TreeNode left; // TreeNode right;Explore the full code

solution.javaJava

Generic Tree LCA — Recurse Both Subtrees — reference

3 teaching notes

1
// Definition for a binary tree node.
2
// class TreeNode {
3
//     int val;
4
//     TreeNode left;
5
//     TreeNode right;
6
//     TreeNode(int x) { val = x; }
7
// }
8
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
9
    // Base case: an empty subtree returns null; hitting p or q reports that target
10
    // upward.
11
    if (root == null || root == p || root == q) {
12
        return root;
13
    }
14
    TreeNode left = lowestCommonAncestor(root.left, p, q);
15
    TreeNode right = lowestCommonAncestor(root.right, p, q);
16
    // Both targets found on opposite sides → this node is the split point, i.e. the
17
    // LCA.
18
    if (left != null && right != null) {
19
        return root;
20
    }
21
    // Otherwise propagate whichever side found something (or null if neither did).
22
    return left != null ? left : right;
23
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.23 lines

D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proof

The generic method finds the LCA by detecting the node where the two targets first appear on different sides. That's the same 'split point' idea as the optimal solution — the BST version just uses value comparisons to find the split in O(h) instead of exploring everything in O(n).

ComplexityO(n) time, O(h) space — In the worst case we visit every node once (we don't use the ordering to prune), so O(n) time; the recursion stack is as deep as the tree, O(h).

E · Edge cases and pitfalls3Using this on a BST and never exploiting the ordering — correct but O(n) instead of O(h).Explore edge cases

Pitfalls

Using this on a BST and never exploiting the ordering — correct but O(n) instead of O(h).
Forgetting the `root == p || root == q` base case, which handles 'a node is its own ancestor'.
Recursing only one side based on a guess — without the BST ordering you must check both.

03.2

Approach 2 of 2 · Optimal

BST Descent — Walk to the Split Point (Optimal)

TimeO(h)SpaceO(1)

The answer they want for a BST. Frame it as 'use the ordering to pick a direction, stop at the split'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You're on a sorted tree. If both p and q are larger than the current node, where can they possibly be?

2Hint 2Explore hint

If both targets are greater than node.val, go right; if both are smaller, go left. What does it mean when they're on opposite sides?

3Hint 3Explore hint

The first node where p and q are NOT both on the same side is their LCA — that includes the case where node equals p or q. Loop until you hit it.

A · Core idea

On a BST we never need to look at both children. The ordering tells us which single direction can contain both targets, so we descend a single root-to-node path until the targets diverge.

The split-point insight. Pick any node on the path from the root. If p and q are both greater than it, both live in its right subtree, so the LCA must be further right. If both are smaller, both live left. The only remaining case is that one target is ≤ node ≤ the other (or one of them equals the node). At that node, the paths to p and q go down different children — this is the lowest node that still has both as descendants, i.e. the LCA. We can stop the instant we reach it.

Why this is O(h), not O(n). Each comparison lets us discard an entire subtree, so we touch one node per level and never branch. That collapses the search from 'visit everything' to 'follow one path', exactly like an ordinary BST search for a value.

Why iterative beats recursive here. The recursion is tail-recursive — the recursive call is the last thing each frame does — so it carries no useful stack information. Rewriting it as a while loop reuses a single pointer variable and brings space down from O(h) to O(1). State that trade explicitly; it's the kind of detail interviewers reward.

Why we never run off the tree. The problem guarantees both p and q exist, so a split point always lies on the shared prefix of their two root-paths. We are guaranteed to return before node becomes null.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Interactive diagram

Descending to the split point

node = 6

Active call / nodeSupporting contextReturned stateNot active

Searching for p=2 and q=8 on the example BST: both target paths share only the root before diverging.

Final result2

C · Code with teaching comments

solution.javaJava

BST Descent — Walk to the Split Point (Optimal) — optimal

3 teaching notes

1
// Definition for a binary tree node.
2
// class TreeNode {
3
//     int val;
4
//     TreeNode left;
5
//     TreeNode right;
6
//     TreeNode(int x) { val = x; }
7
// }
8
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
9
    TreeNode node = root;
10
    while (node != null) {
11
        // Both targets larger → both live in the right subtree, so the LCA is to the
12
        // right.
13
        if (p.val > node.val && q.val > node.val) {
14
            node = node.right;
15
        // Both targets smaller → descend left.
16
        } else if (p.val < node.val && q.val < node.val) {
17
            node = node.left;
18
        } else {
19
            // Targets split (or one equals node) → this is the lowest common ancestor.
20
            return node;
21
        }
22
    }
23
    return null;
24
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.24 lines

D · Why it works and complexityO(h) timeO(1) spaceOpen the invariant and proofExplore the proof

The LCA on a BST is the unique node whose value lies between p.val and q.val inclusive, and is closest to the root among such nodes — equivalently, the first node where the two search paths diverge. Recognising 'LCA = first divergence of two BST searches' is the entire trick.

ComplexityO(h) time, O(1) space — Each step moves one level down the tree and does O(1) comparison work, so the cost is the height h (O(log n) balanced, O(n) degenerate). Iterating uses no extra stack → O(1) space.

E · Edge cases and pitfalls6p is an ancestor of q (e.g. p=2, q=4) — When node reaches 2, q is greater and p equals node → the else branch returns 2. A node is its own ancestor.Explore edge cases

Edge cases handled

p is an ancestor of q (e.g. p=2, q=4)When node reaches 2, q is greater and p equals node → the else branch returns 2. A node is its own ancestor.
p and q are the two children of the root (p=2, q=8 under 6)At the root, one target is smaller and one larger → split immediately, root is the LCA.
Skewed tree, p and q deep on the same sideWe follow that side level by level — O(h) which may be O(n) for a degenerate BST, still optimal for this shape.

Pitfalls

Flipping the comparison directions so you walk away from the targets.
Using strict `>`/`<` but forgetting the equality case lands in the else branch (which is exactly what handles node == p or node == q).
Recursing instead of looping — correct, but wastes O(h) stack for a tail-recursive walk.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code preview// Definition for a binary tree node. // class TreeNode { // int val; // TreeNode left; // TreeNode right;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Ignoring the BST ordering

Recursing into both subtrees works but is O(n). On a BST a single comparison discards half the tree, giving O(h). Interviewers expect you to use the property you were handed.

Explore the code comparison

Don't write this

def lca(node, p, q):
    if not node or node is p or node is q:
        return node
    left = lca(node.left, p, q)
    right = lca(node.right, p, q)
    return node if left and right else (left or right)

Write this instead

node = root
while node:
    if p.val > node.val and q.val > node.val:
        node = node.right
    elif p.val < node.val and q.val < node.val:
        node = node.left
    else:
        return node

Missing the equality (self-ancestor) case

If you only branch on strict greater/less and treat 'node equals a target' as a separate special case, you complicate the code. Letting equality fall through to the else branch returns the node correctly — a node is its own ancestor.

Explore the code comparison

Don't write this

if (p.val == node.val || q.val == node.val) {
    // forgot this returns node; falls through and loops forever
}
if (p.val > node.val && q.val > node.val) node = node.right;
else node = node.left;

Write this instead

if (p.val > node.val && q.val > node.val) node = node.right;
else if (p.val < node.val && q.val < node.val) node = node.left;
else return node; // covers split AND node == p/q

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

BST-guided descent (split point)

Code pattern to memorize

node = root
while node:
    if p.val < node.val and q.val < node.val: node = node.left
    elif p.val > node.val and q.val > node.val: node = node.right
    else: return node   # split or match → LCA

Rules to remember

1Use the BST ordering — don't fall back to the generic O(n) LCA search you'd use on a plain binary tree.
2The LCA is the first node where p and q diverge (one ≤ node ≤ other), including the case where node equals p or q.
3Both-greater → go right; both-smaller → go left; anything else → return node.
4Iterate with O(1) space — the recursion is tail-recursive, so a while loop is strictly better.
5The problem guarantees both nodes exist in the tree, so you never walk off the end before finding the answer.

Use this pattern when

Finding the LCA in a **binary search tree** specifically (values are ordered)
You can compare target values against the current node to pick a direction
You want O(h) rather than O(n) and don't need to handle arbitrary binary trees
Ancestor / range / 'where do two paths from the root diverge?' questions on a BST

Choose another pattern when

Tree is a **plain binary tree** (no ordering) → use the recursive return-up LCA (LeetCode 236)
Nodes might **not exist** in the tree → you must verify presence, not just split
You need the LCA of more than two nodes or a forest → different formulation
It's a general graph, not a tree → use binary lifting / Tarjan's offline LCA

Interview takeaway

On a BST, the LCA is simply the split point: the first node from the root that sits between `p` and `q` in value. Comparing against the node's value to choose a direction turns an O(n) tree walk into an O(h) descent — the same 'let the ordering guide you' idea behind Validate BST and Kth Smallest in a BST.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternBST-guided descent. Whenever the tree is ordered, compare the target(s) against the current node to discard a whole subtree per step, turning an O(n) tree walk into an O(h) path. Same family as Search in a BST, Validate BST, and Kth Smallest in a BST.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Lowest Common Ancestor of a Binary Tree
Coming soon
No ordering — use the generic recurse-both-subtrees method that returns the split node.
Validate Binary Search Tree
Same 'let the ordering guide you' idea — carry value bounds down the tree.
Lowest Common Ancestor of a Binary Tree II
Coming soon
Nodes may not exist — you must confirm both p and q are actually present.
Search in a Binary Search Tree
Coming soon
The same single-path BST descent, just searching for one value instead of a split.

Same pattern

←

Subtree of Another Tree

Continue · Next problem

Binary Tree Level Order Traversal

mediumTreesLC #235Frequently asked

Lowest Common Ancestor of a BST

LCPractice

Trees & BST · 8 of 41 · 8 min

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes p and q in the BST.

The lowest common ancestor is defined between two nodes p and q as the lowest node in the tree that has both p and q as descendants (where we allow **a node to be a descendant of itself**).

Both p and q exist in the BST and all node values are unique.

In plain English

Examples

Example 1

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Note: 2 is in the left subtree of 6 and 8 is in the right subtree, so they split at the root — 6 is the LCA.

Example 2

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Note: 4 lives in the subtree rooted at 2, so 2 is an ancestor of itself and of 4 — the LCA is 2.

Example 3

Input: root = [2,1], p = 2, q = 1
Output: 2
Note: 1 is the left child of 2; 2 is its own ancestor, so the LCA is 2.

Constraints

The number of nodes is in the range [2, 10⁵]
-10⁹ ≤ Node.val ≤ 10⁹
All Node.val are unique
p ≠ q, and both p and q exist in the BST

Clarifying questions4First question: Is the tree guaranteed to be a valid BST?Explore questions

Q1.Is the tree guaranteed to be a valid BST?
Yes — that's the whole point. The ordering invariant is what lets us pick a direction by comparing values instead of searching both subtrees.
Q2.Are p and q guaranteed to be present in the tree?
Yes. Because both exist, the descent always reaches a valid split point — we never need to verify existence separately.
Q3.Can a node be an ancestor of itself?
Yes. If p is an ancestor of q (or p == the split node), then p itself is the LCA. The 'else' branch covers node == p or node == q.
Q4.Are the values unique?
Yes, so comparing `p.val`/`q.val` against `node.val` is unambiguous — there's never a tie to break.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognize that the BST invariant lets you prune to a single root-to-node path instead of searching the whole tree — and whether you can express the descent in O(1) space.

Where candidates slip

Writing the generic O(n) binary-tree LCA (recursing both subtrees) and ignoring the BST ordering entirely, or getting the comparison directions backwards so you walk away from the answer.

How to stand out

Name the split-point insight out loud, do it iteratively in O(1) space, and contrast it with the LeetCode 236 plain-tree version to show you know exactly which property you're exploiting.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Generic Tree LCA — Recurse Both Subtrees	`O(n)`	`O(h)`	Mention it as the fallback that works on any binary tree, then point out it ignores the BST ordering and is therefore slower than necessary.	Read
2	BST Descent — Walk to the Split Point (Optimal)Optimal	`O(h)`	`O(1)`	The answer they want for a BST. Frame it as 'use the ordering to pick a direction, stop at the split'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Generic Tree LCA — Recurse Both Subtrees

TimeO(n)SpaceO(h)

Mention it as the fallback that works on any binary tree, then point out it ignores the BST ordering and is therefore slower than necessary.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Forget the ordering for a second: on a plain binary tree, how would you know whether a subtree contains p, q, or both?

2Hint 2Explore hint

Recurse into left and right. If p and q come back from different sides, the current node is the LCA.

3Hint 3Explore hint

If both come back from the same side, the LCA is deeper on that side; if neither side has them, return null up the chain.

A · Core idea

This is the universal LCA algorithm — it works on any binary tree, ordered or not. It searches the tree bottom-up and lets each node report whether p or q was found beneath it.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

root = [6,2,8,0,4,7,9], p = 2, q = 8

node 6

recurse left (subtree of 2) and right (subtree of 8)

Statewaiting on both children

Final result6

C · Code with teaching comments

Reference implementation preview// Definition for a binary tree node. // class TreeNode { // int val; // TreeNode left; // TreeNode right;Explore the full code

solution.javaJava

Generic Tree LCA — Recurse Both Subtrees — reference

3 teaching notes

1
// Definition for a binary tree node.
2
// class TreeNode {
3
//     int val;
4
//     TreeNode left;
5
//     TreeNode right;
6
//     TreeNode(int x) { val = x; }
7
// }
8
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
9
    // Base case: an empty subtree returns null; hitting p or q reports that target
10
    // upward.
11
    if (root == null || root == p || root == q) {
12
        return root;
13
    }
14
    TreeNode left = lowestCommonAncestor(root.left, p, q);
15
    TreeNode right = lowestCommonAncestor(root.right, p, q);
16
    // Both targets found on opposite sides → this node is the split point, i.e. the
17
    // LCA.
18
    if (left != null && right != null) {
19
        return root;
20
    }
21
    // Otherwise propagate whichever side found something (or null if neither did).
22
    return left != null ? left : right;
23
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.23 lines

D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(h) space — In the worst case we visit every node once (we don't use the ordering to prune), so O(n) time; the recursion stack is as deep as the tree, O(h).

E · Edge cases and pitfalls3Using this on a BST and never exploiting the ordering — correct but O(n) instead of O(h).Explore edge cases

Pitfalls

Using this on a BST and never exploiting the ordering — correct but O(n) instead of O(h).
Forgetting the `root == p || root == q` base case, which handles 'a node is its own ancestor'.
Recursing only one side based on a guess — without the BST ordering you must check both.

03.2

Approach 2 of 2 · Optimal

BST Descent — Walk to the Split Point (Optimal)

TimeO(h)SpaceO(1)

The answer they want for a BST. Frame it as 'use the ordering to pick a direction, stop at the split'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You're on a sorted tree. If both p and q are larger than the current node, where can they possibly be?

2Hint 2Explore hint

If both targets are greater than node.val, go right; if both are smaller, go left. What does it mean when they're on opposite sides?

3Hint 3Explore hint

The first node where p and q are NOT both on the same side is their LCA — that includes the case where node equals p or q. Loop until you hit it.

A · Core idea

On a BST we never need to look at both children. The ordering tells us which single direction can contain both targets, so we descend a single root-to-node path until the targets diverge.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Interactive diagram

Descending to the split point

node = 6

Active call / nodeSupporting contextReturned stateNot active

Searching for p=2 and q=8 on the example BST: both target paths share only the root before diverging.

Final result2

C · Code with teaching comments

solution.javaJava

BST Descent — Walk to the Split Point (Optimal) — optimal

3 teaching notes

1
// Definition for a binary tree node.
2
// class TreeNode {
3
//     int val;
4
//     TreeNode left;
5
//     TreeNode right;
6
//     TreeNode(int x) { val = x; }
7
// }
8
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
9
    TreeNode node = root;
10
    while (node != null) {
11
        // Both targets larger → both live in the right subtree, so the LCA is to the
12
        // right.
13
        if (p.val > node.val && q.val > node.val) {
14
            node = node.right;
15
        // Both targets smaller → descend left.
16
        } else if (p.val < node.val && q.val < node.val) {
17
            node = node.left;
18
        } else {
19
            // Targets split (or one equals node) → this is the lowest common ancestor.
20
            return node;
21
        }
22
    }
23
    return null;
24
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.24 lines

D · Why it works and complexityO(h) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6p is an ancestor of q (e.g. p=2, q=4) — When node reaches 2, q is greater and p equals node → the else branch returns 2. A node is its own ancestor.Explore edge cases

Edge cases handled

p is an ancestor of q (e.g. p=2, q=4)When node reaches 2, q is greater and p equals node → the else branch returns 2. A node is its own ancestor.
p and q are the two children of the root (p=2, q=8 under 6)At the root, one target is smaller and one larger → split immediately, root is the LCA.
Skewed tree, p and q deep on the same sideWe follow that side level by level — O(h) which may be O(n) for a degenerate BST, still optimal for this shape.

Pitfalls

Flipping the comparison directions so you walk away from the targets.
Using strict `>`/`<` but forgetting the equality case lands in the else branch (which is exactly what handles node == p or node == q).
Recursing instead of looping — correct, but wastes O(h) stack for a tail-recursive walk.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code preview// Definition for a binary tree node. // class TreeNode { // int val; // TreeNode left; // TreeNode right;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Ignoring the BST ordering

Recursing into both subtrees works but is O(n). On a BST a single comparison discards half the tree, giving O(h). Interviewers expect you to use the property you were handed.

Explore the code comparison

Don't write this

def lca(node, p, q):
    if not node or node is p or node is q:
        return node
    left = lca(node.left, p, q)
    right = lca(node.right, p, q)
    return node if left and right else (left or right)

Write this instead

node = root
while node:
    if p.val > node.val and q.val > node.val:
        node = node.right
    elif p.val < node.val and q.val < node.val:
        node = node.left
    else:
        return node

Missing the equality (self-ancestor) case

Explore the code comparison

Don't write this

if (p.val == node.val || q.val == node.val) {
    // forgot this returns node; falls through and loops forever
}
if (p.val > node.val && q.val > node.val) node = node.right;
else node = node.left;

Write this instead

if (p.val > node.val && q.val > node.val) node = node.right;
else if (p.val < node.val && q.val < node.val) node = node.left;
else return node; // covers split AND node == p/q

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

BST-guided descent (split point)

Code pattern to memorize

node = root
while node:
    if p.val < node.val and q.val < node.val: node = node.left
    elif p.val > node.val and q.val > node.val: node = node.right
    else: return node   # split or match → LCA

Rules to remember

1Use the BST ordering — don't fall back to the generic O(n) LCA search you'd use on a plain binary tree.
2The LCA is the first node where p and q diverge (one ≤ node ≤ other), including the case where node equals p or q.
3Both-greater → go right; both-smaller → go left; anything else → return node.
4Iterate with O(1) space — the recursion is tail-recursive, so a while loop is strictly better.
5The problem guarantees both nodes exist in the tree, so you never walk off the end before finding the answer.

Use this pattern when

Finding the LCA in a **binary search tree** specifically (values are ordered)
You can compare target values against the current node to pick a direction
You want O(h) rather than O(n) and don't need to handle arbitrary binary trees
Ancestor / range / 'where do two paths from the root diverge?' questions on a BST

Choose another pattern when

Tree is a **plain binary tree** (no ordering) → use the recursive return-up LCA (LeetCode 236)
Nodes might **not exist** in the tree → you must verify presence, not just split
You need the LCA of more than two nodes or a forest → different formulation
It's a general graph, not a tree → use binary lifting / Tarjan's offline LCA

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Lowest Common Ancestor of a Binary Tree
Coming soon
No ordering — use the generic recurse-both-subtrees method that returns the split node.
Validate Binary Search Tree
Same 'let the ordering guide you' idea — carry value bounds down the tree.
Lowest Common Ancestor of a Binary Tree II
Coming soon
Nodes may not exist — you must confirm both p and q are actually present.
Search in a Binary Search Tree
Coming soon
The same single-path BST descent, just searching for one value instead of a split.

Same pattern

←

Subtree of Another Tree

Continue · Next problem

Binary Tree Level Order Traversal