Loading…

easyTreesFrequently asked

Binary Search Tree: Lowest Common Ancestor

Q: How do you solve Binary Search Tree: Lowest Common Ancestor using the Brute Force — Store Both Root-to-Node Paths approach?

When to use it: Mention as the general-tree fallback that ignores the BST property — then show the ordering lets you skip the path storage. This is the approach that works for *any* binary tree, BST or not, and it's worth stating to show you know the general technique before specializing. **Find the two paths.** Compute the list of nodes from the root down to `v1`, and separately from the root down to `v2`. In a general tree this means a search; in a BST you could use the ordering, but the brute-force framing assumes you don't. **Compare the paths.** Both paths start at the root and share a common prefix. Walk them in lockstep while the nodes match; the *last* matching node before they diverge is the lowest common ancestor. Everything after that point goes into different subtrees. **Why we can do better on a BST.** Storing two full paths costs O(n) memory, and you make two separate descents. The BST ordering lets you do a *single* descent and detect the divergence on the fly — no path lists, O(1) space. That's the optimization the next approach captures. Time complexity: O(n). Space complexity: O(n).

Q: How do you solve Binary Search Tree: Lowest Common Ancestor using the BST Guided Descent — Split Point (Optimal) approach?

When to use it: The answer they want. One descent, O(1) space, using the ordering. In a BST, searching for a value is a sequence of left/right turns dictated by comparisons. The LCA of two values is precisely the node at which their two searches *first diverge*. **The three cases at each node.** Compare both targets `a` and `b` against the current node's value: 1. **Both smaller** (`a node` and `b > node`): both turn right — move to `node.right`. 3. **Otherwise** (one is ≤ and the other is ≥, i.e. they split, or one equals the node): the two searches part ways here — this node is the LCA, so return it. **Why the split point is the answer.** Up to this node, both targets shared every turn, meaning both live in the same subtree at each step — this node is a common ancestor. The moment they diverge, one target is in the left subtree (or is this node) and the other in the right (or is this node), so no deeper node can be ancestor to *both*. Hence this is the *lowest* common ancestor. **Ancestor-of-itself case.** If one target equals the current node, case 3 fires (it's neither strictly-both-less nor strictly-both-greater), and we correctly return that node — matching the rule that a node is its own ancestor. **Why O(1) space.** Unlike the brute force, we never store the paths; we detect divergence as we walk, keeping just one pointer. The descent stops at the LCA, never going below it. Time complexity: O(h). Space complexity: O(1).

Trees & BST · 32 of 41 · 8 min

Given the root of a binary search tree and two node values v1 and v2, return the lowest common ancestor (LCA) of the two nodes — the deepest node that has both v1 and v2 as descendants (a node is a descendant of itself).

You may assume both values exist in the tree.

In plain English

The LCA of two nodes is the deepest node from which one target lies in (or is) the left subtree and the other in (or is) the right subtree — the point where their two root-to-node paths diverge. In a BST, the sorted ordering tells us which way each search would go, so we can walk straight to that divergence point.

Examples

Example 1

Input: BST root 6 with subtrees {2:{0,4:{3,5}}, 8:{7,9}}, v1=2, v2=8
Output: 6
Note: 2 < 6 and 8 > 6 — they split at the root, so the LCA is 6.

Example 2

Input: same BST, v1=3, v2=5
Output: 4
Note: Both < 6 → go left to 2; both > 2 → go right to 4; 3 < 4 and 5 > 4 → split at 4.

Example 3

Input: same BST, v1=2, v2=4
Output: 2
Note: 4 > 6? no, both < 6 → left to 2. Now one target IS 2 → 2 is an ancestor of 4, so LCA = 2.

Constraints

1 ≤ number of nodes ≤ 10000
1 ≤ node value ≤ 10000
All node values are unique (it is a valid BST)
Both v1 and v2 are guaranteed to be present in the tree

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

Q1.Is the tree guaranteed to be a BST?
Yes — that's the whole point. The ordering lets us pick a direction at each node instead of searching both subtrees, dropping the cost from O(n) to O(h).
Q2.Can one node be an ancestor of the other?
Yes. A node is its own ancestor, so if v1 is an ancestor of v2, the LCA is v1 — handled naturally because one target equals the current node at the split.
Q3.Are both values guaranteed to exist?
The problem assumes so. If they might be absent, add a search to confirm presence first, since plain descent would otherwise return a node that isn't a true common ancestor.
Q4.Do I return the node or its value?
Return the node (pointer). HackerRank's signature returns the node; print or read its value as needed.

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 compare both target values to the current node. If both are smaller, the LCA is in the left subtree; if both are larger, it's in the right. The first node where the two targets fall on different sides (or one equals the node) is the lowest common ancestor — that's the split point. It runs in O(h) time and O(1) space, with no extra path storage. The general-binary-tree LCA is O(n); here the BST property makes it a guided descent.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you exploit the BST ordering to find the LCA in O(h) without storing paths, rather than running the general O(n) tree algorithm.

Where candidates slip

Using the generic LCA (searching both subtrees) and ignoring the BST property, or mishandling the case where one target equals the current node (it should be the LCA).

How to stand out

State that the LCA is the split point of two BST searches, derive the three-way comparison, and note the O(1) space win over the general-tree path-storing approach.

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	Brute Force — Store Both Root-to-Node Paths	`O(n)`	`O(n)`	Mention as the general-tree fallback that ignores the BST property — then show the ordering lets you skip the path storage.	Read
2	BST Guided Descent — Split Point (Optimal)Optimal	`O(h)`	`O(1)`	The answer they want. One descent, O(1) space, using the ordering.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewnode, targets a,bboth < node?YesNoExplore the full tree

Three-way comparison at each node

How to read it:Both smaller → left; both larger → right; otherwise this node is the split point (the LCA).

Rendering diagram…

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

Brute Force — Store Both Root-to-Node Paths

TimeO(n)SpaceO(n)

Mention as the general-tree fallback that ignores the BST property — then show the ordering lets you skip the path storage.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Forget the ordering for a moment: how would you find the LCA in ANY binary tree given two node values?

2Hint 2Explore hint

Record the path from the root to each target as a list of nodes.

3Hint 3Explore hint

Walk both paths in parallel from the root; the last node they share is the LCA.

A · Core idea

This is the approach that works for any binary tree, BST or not, and it's worth stating to show you know the general technique before specializing.

Find the two paths. Compute the list of nodes from the root down to v1, and separately from the root down to v2. In a general tree this means a search; in a BST you could use the ordering, but the brute-force framing assumes you don't.

Compare the paths. Both paths start at the root and share a common prefix. Walk them in lockstep while the nodes match; the last matching node before they diverge is the lowest common ancestor. Everything after that point goes into different subtrees.

Why we can do better on a BST. Storing two full paths costs O(n) memory, and you make two separate descents. The BST ordering lets you do a single descent and detect the divergence on the fly — no path lists, O(1) space. That's the optimization the next approach captures.

B · Visual dry run

Interactive dry run

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

BST root 6, v1=3, v2=5

Interactive diagram

Two paths share a prefix

path to 3

Active call / nodeSupporting contextReturned stateNot active

Paths to 3 and 5 share 6,2,4 then split — 4 is the LCA.

Final result4

C · Code with teaching comments

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

solution.javaJava

Brute Force — Store Both Root-to-Node Paths — reference

4 teaching notes

1
// Definition for a binary tree node.
2
class Node {
3
    int data;
4
    Node left;
5
    Node right;
6
}
7
 
8
public Node lca(Node root, int v1, int v2) {
9
    List<Node> path1 = new ArrayList<>();
10
    List<Node> path2 = new ArrayList<>();
11
    // Record the root-to-v1 node sequence.
12
    findPath(root, v1, path1);
13
    findPath(root, v2, path2);
14
    Node ancestor = null;
15
    int i = 0;
16
    while (i < path1.size() && i < path2.size() && path1.get(i) == path2.get(i)) {
17
        ancestor = path1.get(i);   // last shared node so far
18
        i++;
19
    }
20
    return ancestor;
21
}
22
 
23
private boolean findPath(Node node, int target, List<Node> path) {
24
    if (node == null) return false;
25
    path.add(node);
26
    if (node.data == target) return true;
27
    if (findPath(node.left, target, path) || findPath(node.right, target, path)) {
28
        return true;
29
    }
30
    path.remove(path.size() - 1);  // backtrack
31
    return false;
32
}

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

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

The LCA is, by definition, the last shared node of two root-to-target paths. Seeing it that way makes the BST optimization obvious: we don't need to store the paths if the ordering tells us, at each step, whether the two paths still agree on a direction.

ComplexityO(n) time, O(n) space — Building each path may visit up to O(n) nodes (in a general search) and the paths take O(n) space; comparing them is O(h). Total O(n) time and O(n) space.

E · Edge cases and pitfalls5v1 == v2 — Both paths identical → the node itself is the LCA.Explore edge cases

Edge cases handled

v1 == v2Both paths identical → the node itself is the LCA.
One target is the rootShared prefix is just the root → LCA is the root.

Pitfalls

Comparing path nodes by value instead of identity when values are unique it's fine, but identity (==) is safest.
Forgetting to backtrack in findPath — paths get polluted with dead-end nodes.
Using O(n) space when the BST property makes O(1) possible.

03.2

Approach 2 of 2 · Optimal

BST Guided Descent — Split Point (Optimal)

TimeO(h)SpaceO(1)

The answer they want. One descent, O(1) space, using the ordering.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

At the root, where would a BST search for v1 go? Where would a search for v2 go? When do those two searches first take different turns?

2Hint 2Explore hint

If both targets are less than the current node, both searches go left; if both are greater, both go right.

3Hint 3Explore hint

The first node where the targets fall on opposite sides — or where one equals the node — is the LCA. Return it.

A · Core idea

In a BST, searching for a value is a sequence of left/right turns dictated by comparisons. The LCA of two values is precisely the node at which their two searches first diverge.

The three cases at each node. Compare both targets a and b against the current node's value:

1
Both smaller (a < node and b < node): both searches turn left, so the LCA must be deeper on the left — move to node.left.
2
Both larger (a > node and b > node): both turn right — move to node.right.
3
Otherwise (one is ≤ and the other is ≥, i.e. they split, or one equals the node): the two searches part ways here — this node is the LCA, so return it.

Why the split point is the answer. Up to this node, both targets shared every turn, meaning both live in the same subtree at each step — this node is a common ancestor. The moment they diverge, one target is in the left subtree (or is this node) and the other in the right (or is this node), so no deeper node can be ancestor to both. Hence this is the lowest common ancestor.

Ancestor-of-itself case. If one target equals the current node, case 3 fires (it's neither strictly-both-less nor strictly-both-greater), and we correctly return that node — matching the rule that a node is its own ancestor.

Why O(1) space. Unlike the brute force, we never store the paths; we detect divergence as we walk, keeping just one pointer. The descent stops at the LCA, never going below it.

B · Visual dry run

Interactive dry run

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

BST root 6, v1=3, v2=5

Interactive diagram

Descent for LCA(3,5)

node 6

Active call / nodeSupporting contextReturned stateNot active

6 (both left) → 2 (both right) → 4 (split) — return 4.

Final result4

C · Code with teaching comments

solution.javaJava

BST Guided Descent — Split Point (Optimal) — optimal

3 teaching notes

1
public Node lca(Node root, int v1, int v2) {
2
    Node node = root;
3
    while (node != null) {
4
        if (v1 < node.data && v2 < node.data) {
5
            node = node.left;          // both targets smaller → go left
6
        } else if (v1 > node.data && v2 > node.data) {
7
            node = node.right;         // both targets larger → go right
8
        } else {
9
            return node;               // split point (or one equals node) → LCA
10
        }
11
    }
12
    return null;                       // unreachable if both values exist
13
}

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

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

LCA on a BST = 'walk down until the two keys want to go different directions.' The sorted property converts a two-subtree search into a single guided descent — the canonical example of letting structure replace search.

ComplexityO(h) time, O(1) space — You descend a single root-to-LCA path doing O(1) comparison per level → O(h) time. Only a single pointer is kept → O(1) space (no recursion, no path lists).

E · Edge cases and pitfalls6LCA(2,8) at root 6 — 2 < 6, 8 > 6 → split at root → 6.Explore edge cases

Edge cases handled

LCA(2,8) at root 62 < 6, 8 > 6 → split at root → 6.
LCA(2,4) where 2 is ancestor of 4Descend to 2; v1 equals node → return 2.
v1 == v2 == xNeither both-less nor both-greater at the node holding x → returns that node.

Pitfalls

Using strict < on one side and <= on the other inconsistently — breaks the ancestor-of-itself case.
Recursing into both subtrees like the general-tree LCA — wastes the BST property.
Assuming targets exist without checking when the problem doesn't guarantee it.

Practice

Try the solution yourself

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

Editable code previewpublic Node lca(Node root, int v1, int v2) { Node node = root; while (node != null) { if (v1 < node.data && v2 < node.data) { node = node.left; // both targets smaller → go leftExplore 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 property

The generic LCA searches both subtrees at every node, costing O(n). On a BST the ordering tells you which single direction to take, so you should descend, not search.

Explore the code comparison

Don't write this

Node lca(Node n, int a, int b) {       // general-tree version on a BST
    if (n == null || n.data == a || n.data == b) return n;
    Node l = lca(n.left, a, b);
    Node r = lca(n.right, a, b);
    return (l != null && r != null) ? n : (l != null ? l : r);
}

Write this instead

Node lca(Node node, int a, int b) {     // BST-guided descent, O(h)
    while (node != null) {
        if (a < node.data && b < node.data) node = node.left;
        else if (a > node.data && b > node.data) node = node.right;
        else return node;
    }
    return null;
}

Breaking the ancestor-of-itself case

If one target equals the current node, that node IS the LCA. Using strict-both-less / strict-both-greater leaves equality to fall into the else branch correctly; mixing in <= can skip past the true LCA.

Explore the code comparison

Don't write this

if v1 <= node.data and v2 <= node.data:   # <= can descend past an equal target
    node = node.left

Write this instead

if v1 < node.data and v2 < node.data:      # strict: equal target triggers the split
    node = node.left

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Guided BST descent until the two targets split

Code pattern to memorize

lca(root, a, b):
    node = root
    while node:
        if a < node.data and b < node.data: node = node.left
        elif a > node.data and b > node.data: node = node.right
        else: return node   # split point (or one equals node)

Rules to remember

1Both targets smaller → go left; both larger → go right.
2The split point (targets diverge, or one equals the node) is the LCA — return it immediately.
3Works because a BST sorts values left-to-right, so the LCA is the last shared step of two searches.
4O(h) time, O(1) space — no need to store root-to-node paths like the general-tree solution.
5A node is an ancestor of itself, so if one target IS an ancestor of the other, that node is the LCA.

Use this pattern when

LCA when the tree is a BST (ordering lets you skip the O(n) search)
Finding the split point of two BST search paths
Range/interval queries that pivot on where two keys diverge

Choose another pattern when

The tree is NOT a BST → general LCA recursion (search both subtrees), O(n)
Many repeated LCA queries on a static tree → preprocess with binary lifting / Euler tour + RMQ
Targets may be absent → add an existence check; plain descent assumes both are present

Interview takeaway

On a BST, LCA is the point where two downward searches part ways. Comparing both targets to each node turns an O(n) tree search into an O(h) guided walk with no extra memory — the cleanest payoff of the sorted-tree property.

Continue

Transfer the pattern to another problem

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

Transferable patternGuided BST descent to a split point. Because a BST orders values left-to-right, the LCA of two keys is the first node where their searches diverge — found in a single O(h), O(1)-space walk. This is the structure-replaces-search payoff; the general (non-BST) LCA must search both subtrees in O(n).

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

←

Binary Search Tree: Insertion

Continue · Next problem

Is This a Binary Search Tree?

easyTreesFrequently asked

Binary Search Tree: Lowest Common Ancestor

Trees & BST · 32 of 41 · 8 min

You may assume both values exist in the tree.

In plain English

Examples

Example 1

Input: BST root 6 with subtrees {2:{0,4:{3,5}}, 8:{7,9}}, v1=2, v2=8
Output: 6
Note: 2 < 6 and 8 > 6 — they split at the root, so the LCA is 6.

Example 2

Input: same BST, v1=3, v2=5
Output: 4
Note: Both < 6 → go left to 2; both > 2 → go right to 4; 3 < 4 and 5 > 4 → split at 4.

Example 3

Input: same BST, v1=2, v2=4
Output: 2
Note: 4 > 6? no, both < 6 → left to 2. Now one target IS 2 → 2 is an ancestor of 4, so LCA = 2.

Constraints

1 ≤ number of nodes ≤ 10000
1 ≤ node value ≤ 10000
All node values are unique (it is a valid BST)
Both v1 and v2 are guaranteed to be present in the tree

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

Q1.Is the tree guaranteed to be a BST?
Yes — that's the whole point. The ordering lets us pick a direction at each node instead of searching both subtrees, dropping the cost from O(n) to O(h).
Q2.Can one node be an ancestor of the other?
Yes. A node is its own ancestor, so if v1 is an ancestor of v2, the LCA is v1 — handled naturally because one target equals the current node at the split.
Q3.Are both values guaranteed to exist?
The problem assumes so. If they might be absent, add a search to confirm presence first, since plain descent would otherwise return a node that isn't a true common ancestor.
Q4.Do I return the node or its value?
Return the node (pointer). HackerRank's signature returns the node; print or read its value as needed.

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 exploit the BST ordering to find the LCA in O(h) without storing paths, rather than running the general O(n) tree algorithm.

Where candidates slip

Using the generic LCA (searching both subtrees) and ignoring the BST property, or mishandling the case where one target equals the current node (it should be the LCA).

How to stand out

State that the LCA is the split point of two BST searches, derive the three-way comparison, and note the O(1) space win over the general-tree path-storing approach.

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	Brute Force — Store Both Root-to-Node Paths	`O(n)`	`O(n)`	Mention as the general-tree fallback that ignores the BST property — then show the ordering lets you skip the path storage.	Read
2	BST Guided Descent — Split Point (Optimal)Optimal	`O(h)`	`O(1)`	The answer they want. One descent, O(1) space, using the ordering.	Read

Three-way comparison at each node

How to read it:Both smaller → left; both larger → right; otherwise this node is the split point (the LCA).

Rendering diagram…

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

Brute Force — Store Both Root-to-Node Paths

TimeO(n)SpaceO(n)

Mention as the general-tree fallback that ignores the BST property — then show the ordering lets you skip the path storage.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Forget the ordering for a moment: how would you find the LCA in ANY binary tree given two node values?

2Hint 2Explore hint

Record the path from the root to each target as a list of nodes.

3Hint 3Explore hint

Walk both paths in parallel from the root; the last node they share is the LCA.

A · Core idea

This is the approach that works for any binary tree, BST or not, and it's worth stating to show you know the general technique before specializing.

B · Visual dry run

Interactive dry run

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

BST root 6, v1=3, v2=5

Interactive diagram

Two paths share a prefix

path to 3

Active call / nodeSupporting contextReturned stateNot active

Paths to 3 and 5 share 6,2,4 then split — 4 is the LCA.

Final result4

C · Code with teaching comments

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

solution.javaJava

Brute Force — Store Both Root-to-Node Paths — reference

4 teaching notes

1
// Definition for a binary tree node.
2
class Node {
3
    int data;
4
    Node left;
5
    Node right;
6
}
7
 
8
public Node lca(Node root, int v1, int v2) {
9
    List<Node> path1 = new ArrayList<>();
10
    List<Node> path2 = new ArrayList<>();
11
    // Record the root-to-v1 node sequence.
12
    findPath(root, v1, path1);
13
    findPath(root, v2, path2);
14
    Node ancestor = null;
15
    int i = 0;
16
    while (i < path1.size() && i < path2.size() && path1.get(i) == path2.get(i)) {
17
        ancestor = path1.get(i);   // last shared node so far
18
        i++;
19
    }
20
    return ancestor;
21
}
22
 
23
private boolean findPath(Node node, int target, List<Node> path) {
24
    if (node == null) return false;
25
    path.add(node);
26
    if (node.data == target) return true;
27
    if (findPath(node.left, target, path) || findPath(node.right, target, path)) {
28
        return true;
29
    }
30
    path.remove(path.size() - 1);  // backtrack
31
    return false;
32
}

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

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

ComplexityO(n) time, O(n) space — Building each path may visit up to O(n) nodes (in a general search) and the paths take O(n) space; comparing them is O(h). Total O(n) time and O(n) space.

E · Edge cases and pitfalls5v1 == v2 — Both paths identical → the node itself is the LCA.Explore edge cases

Edge cases handled

v1 == v2Both paths identical → the node itself is the LCA.
One target is the rootShared prefix is just the root → LCA is the root.

Pitfalls

Comparing path nodes by value instead of identity when values are unique it's fine, but identity (==) is safest.
Forgetting to backtrack in findPath — paths get polluted with dead-end nodes.
Using O(n) space when the BST property makes O(1) possible.

03.2

Approach 2 of 2 · Optimal

BST Guided Descent — Split Point (Optimal)

TimeO(h)SpaceO(1)

The answer they want. One descent, O(1) space, using the ordering.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

At the root, where would a BST search for v1 go? Where would a search for v2 go? When do those two searches first take different turns?

2Hint 2Explore hint

If both targets are less than the current node, both searches go left; if both are greater, both go right.

3Hint 3Explore hint

The first node where the targets fall on opposite sides — or where one equals the node — is the LCA. Return it.

A · Core idea

In a BST, searching for a value is a sequence of left/right turns dictated by comparisons. The LCA of two values is precisely the node at which their two searches first diverge.

The three cases at each node. Compare both targets a and b against the current node's value:

1
Both smaller (a < node and b < node): both searches turn left, so the LCA must be deeper on the left — move to node.left.
2
Both larger (a > node and b > node): both turn right — move to node.right.
3
Otherwise (one is ≤ and the other is ≥, i.e. they split, or one equals the node): the two searches part ways here — this node is the LCA, so return it.

Why O(1) space. Unlike the brute force, we never store the paths; we detect divergence as we walk, keeping just one pointer. The descent stops at the LCA, never going below it.

B · Visual dry run

Interactive dry run

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

BST root 6, v1=3, v2=5

Interactive diagram

Descent for LCA(3,5)

node 6

Active call / nodeSupporting contextReturned stateNot active

6 (both left) → 2 (both right) → 4 (split) — return 4.

Final result4

C · Code with teaching comments

solution.javaJava

BST Guided Descent — Split Point (Optimal) — optimal

3 teaching notes

1
public Node lca(Node root, int v1, int v2) {
2
    Node node = root;
3
    while (node != null) {
4
        if (v1 < node.data && v2 < node.data) {
5
            node = node.left;          // both targets smaller → go left
6
        } else if (v1 > node.data && v2 > node.data) {
7
            node = node.right;         // both targets larger → go right
8
        } else {
9
            return node;               // split point (or one equals node) → LCA
10
        }
11
    }
12
    return null;                       // unreachable if both values exist
13
}

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

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

E · Edge cases and pitfalls6LCA(2,8) at root 6 — 2 < 6, 8 > 6 → split at root → 6.Explore edge cases

Edge cases handled

LCA(2,8) at root 62 < 6, 8 > 6 → split at root → 6.
LCA(2,4) where 2 is ancestor of 4Descend to 2; v1 equals node → return 2.
v1 == v2 == xNeither both-less nor both-greater at the node holding x → returns that node.

Pitfalls

Using strict < on one side and <= on the other inconsistently — breaks the ancestor-of-itself case.
Recursing into both subtrees like the general-tree LCA — wastes the BST property.
Assuming targets exist without checking when the problem doesn't guarantee it.

Practice

Try the solution yourself

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

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 property

The generic LCA searches both subtrees at every node, costing O(n). On a BST the ordering tells you which single direction to take, so you should descend, not search.

Explore the code comparison

Don't write this

Node lca(Node n, int a, int b) {       // general-tree version on a BST
    if (n == null || n.data == a || n.data == b) return n;
    Node l = lca(n.left, a, b);
    Node r = lca(n.right, a, b);
    return (l != null && r != null) ? n : (l != null ? l : r);
}

Write this instead

Node lca(Node node, int a, int b) {     // BST-guided descent, O(h)
    while (node != null) {
        if (a < node.data && b < node.data) node = node.left;
        else if (a > node.data && b > node.data) node = node.right;
        else return node;
    }
    return null;
}

Breaking the ancestor-of-itself case

Explore the code comparison

Don't write this

if v1 <= node.data and v2 <= node.data:   # <= can descend past an equal target
    node = node.left

Write this instead

if v1 < node.data and v2 < node.data:      # strict: equal target triggers the split
    node = node.left

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Guided BST descent until the two targets split

Code pattern to memorize

lca(root, a, b):
    node = root
    while node:
        if a < node.data and b < node.data: node = node.left
        elif a > node.data and b > node.data: node = node.right
        else: return node   # split point (or one equals node)

Rules to remember

1Both targets smaller → go left; both larger → go right.
2The split point (targets diverge, or one equals the node) is the LCA — return it immediately.
3Works because a BST sorts values left-to-right, so the LCA is the last shared step of two searches.
4O(h) time, O(1) space — no need to store root-to-node paths like the general-tree solution.
5A node is an ancestor of itself, so if one target IS an ancestor of the other, that node is the LCA.

Use this pattern when

LCA when the tree is a BST (ordering lets you skip the O(n) search)
Finding the split point of two BST search paths
Range/interval queries that pivot on where two keys diverge

Choose another pattern when

The tree is NOT a BST → general LCA recursion (search both subtrees), O(n)
Many repeated LCA queries on a static tree → preprocess with binary lifting / Euler tour + RMQ
Targets may be absent → add an existence check; plain descent assumes both are present

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

Same pattern

←

Binary Search Tree: Insertion

Continue · Next problem

Is This a Binary Search Tree?