Difficulty: MediumTrees

Lowest Common Ancestor of a Binary Search Tree

Problem in Plain English

Given a binary search tree with two nodes p and q that both exist in it, return the deepest node that is an ancestor of both. A node counts as its own descendant.

Problem Statement

Given the root of a binary search tree and two nodes p and q, return their lowest common ancestor.

The lowest common ancestor is the deepest node that has both p and q as descendants, where a node counts as a descendant of itself.

Both nodes are guaranteed to exist in the tree, they hold distinct values, and every value in the tree is unique.

Constraints

2 <= number of nodes <= 10^5
-10^9 <= Node.val <= 10^9
All node values are unique
p != q and both p and q exist in the tree

Examples

Example 1

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

Basic split: the paths are [6,2] and [6,8]. Their last common node is 6; neither child subtree contains both targets. The output shows the returned node's value.

Example 2

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

Ancestor case: the paths are [6,2] and [6,2,4]. Node 2 counts as its own descendant, so it is the deepest common ancestor. Strict comparisons must stop when the current node equals a target.

Example 3

Input: root = [2,1], p = 2, q = 1
Output: 2

Minimum-size edge case: the tree has only two nodes. The root 2 is both a target and the parent of 1, so return the existing root node.

Example 4

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

Tricky deeper split with reversed target order: both targets are below 6 on its left, then above 2 on its right. At 4, 5 is larger and 3 is smaller. Return 4; the algorithm must work without assuming p has the smaller value.

Intuition

A common ancestor lies on both root-to-target paths; the lowest one is the last node before those paths diverge. In Example 1, the paths to 2 and 8 share only 6. A BST adds a shortcut: if both target values are smaller than the current value, their shared path continues left; if both are larger, it continues right. At a split, or when the current node is a target, we have reached the answer. Return that original node reference, rather than its value or a new node.

Approaches

Root To Node Paths

Solution Details

Reveal Root To Node Paths: intuition, complexity, and code

Intuition

Find each root-to-target path with a general depth-first search, then compare their shared prefix. Explicit enter and exit frames simulate recursive backtracking: entering adds a node to the current path, while exiting removes it after that subtree has failed to find the target. This works even without BST ordering, but searches may explore irrelevant branches; in Example 1 the search for 8 exhausts the left subtree first.

Step-by-Step Logic

For each target, start a fresh path and an enter frame for the root. In Example 1, enter 6, then 2; finding p returns the path [6,2].
For an entered non-target, schedule its exit frame, then its right child, then its left child. A last-in-first-out stack therefore searches left first, and the exit frame removes the node only after both subtrees finish.
Search separately for q = 8. The path visits 6,2,0, backtracks to 2, explores 4,3,5, then backtracks to 6. Entering 8 returns [6,8].
Compare the two path entries by node identity. At index 0, both references are the root 6, so save it as the latest common ancestor.
Stop at the first mismatch or the end of the shorter path. Example 1 differs at index 1 (2 versus 8), so return the saved original node 6.

Why It Works

Just before an enter frame is handled, the path contains exactly the ancestors of that frame's node. Appending the node extends this invariant; its exit frame restores the ancestor path after both child subtrees finish. Returning immediately on target identity therefore produces the unique root-to-target path. Every common ancestor occurs in the shared prefix of the two paths: after they branch into different children, a tree cannot reconnect. Comparing references until the first mismatch, or until the shorter path ends, returns the last shared node. That node is deepest among all common ancestors, including the case where one target ends the shared prefix.

Dry Run

Root To Node Paths: variable states at each step
Search / event	Path before	Path after	Saved paths / comparison
p: enter 6	[]	[6]	schedule exit 6, enter 8, enter 2
p: enter 2, target found	[6]	[6,2]	pathP = [6,2]; stop p search
q: enter 6	[]	[6]	start fresh search
q: enter 2	[6]	[6,2]	left subtree first
q: enter 0	[6,2]	[6,2,0]	not q; leaf
q: exit 0	[6,2,0]	[6,2]	remove failed branch
q: enter 4	[6,2]	[6,2,4]	explore its children
q: enter 3	[6,2,4]	[6,2,4,3]	not q; leaf
q: exit 3	[6,2,4,3]	[6,2,4]	backtrack
q: enter 5	[6,2,4]	[6,2,4,5]	not q; leaf
q: exit 5	[6,2,4,5]	[6,2,4]	backtrack
q: exit 4	[6,2,4]	[6,2]	subtree finished
q: exit 2	[6,2]	[6]	left subtree finished
q: enter 8, target found	[6]	[6,8]	pathQ = [6,8]; stop q search
compare index 0	pathP[0] = 6	pathQ[0] = 6	identical references; lca = 6
compare index 1	pathP[1] = 2	pathQ[1] = 8	mismatch; break and return node 6

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(h)

Let n be the node count and h the height measured in nodes. Each of two searches enters and exits at most n nodes, and prefix comparison costs at most h, giving O(n) time. The live frame stack has at most a constant number of entries per ancestor; the current path and two saved paths each have at most h references. Peak auxiliary space is O(h), although O(n) small frame objects are allocated over the searches. No tree nodes or child links are copied or changed. Explicit frames avoid call-stack overflow on a 100,000-node chain.

Code

Solution.java

1import java.util.ArrayDeque;2import java.util.ArrayList;3import java.util.Deque;4import java.util.List;5
6// Standalone node contract; omit if the judge already provides TreeNode.7class TreeNode {8    int val;9    TreeNode left, right;10    TreeNode(int val) { this.val = val; }11}12
13class Solution {14    private static class Frame {15        TreeNode node;16        boolean exiting;17        Frame(TreeNode node, boolean exiting) {18            this.node = node;19            this.exiting = exiting;20        }21    }22
23    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {24        List<TreeNode> pathP = findPath(root, p);25        List<TreeNode> pathQ = findPath(root, q);26        TreeNode lca = null;27        for (int i = 0; i < pathP.size() && i < pathQ.size(); i++) {28            // The shared prefix ends at the first different node reference.29            if (pathP.get(i) != pathQ.get(i)) break;30            lca = pathP.get(i);31        }32        return lca;33    }34
35    private List<TreeNode> findPath(TreeNode root, TreeNode target) {36        List<TreeNode> path = new ArrayList<>();37        Deque<Frame> stack = new ArrayDeque<>();38        if (root != null) stack.push(new Frame(root, false));39        while (!stack.isEmpty()) {40            Frame frame = stack.pop();41            if (frame.exiting) {42                // Exit runs after both children, restoring the parent path.43                path.remove(path.size() - 1);44                continue;45            }46            TreeNode node = frame.node;47            path.add(node);48            if (node == target) return path;49            // LIFO: exit last, right after left; preserve the tree itself.50            stack.push(new Frame(node, true));51            if (node.right != null) stack.push(new Frame(node.right, false));52            if (node.left != null) stack.push(new Frame(node.left, false));53        }54        return path;55    }56}

Hints

Hint 1

Values left of a node are smaller and values right of it are larger, so both targets on one side means the answer waits down that side.

Hint 2

When one target is smaller and the other is larger, the current node is where their routes split.

Hint 3

A target equal to the current node also ends the walk, since a node is its own ancestor.

Edge Cases

With only two nodes, the root is the LCA of the two targets, including its own descendant relationship.
One target is an ancestor of the other; stop at that target rather than moving past equality.
Targets lie on opposite sides of the root; return the root without searching its children.
Both targets initially lie on the same side, but split much deeper, as in Example 4. Target order can be reversed.
A 100,000-node skewed BST has linear height; explicit DFS frames and the iterative BST walk both avoid recursive call-stack limits.
Negative and extreme values follow the same ordering rules; direct comparisons need no subtraction and cannot overflow.

Common Mistakes and Interview Tips

Using <= or >= for same-side tests moves past a target that is itself the LCA; use strict comparisons.
Returning curr.val or constructing a new node loses the required original node reference; the example output only displays its value.
Assuming p is smaller than q breaks reversed target pairs. Test both targets independently against the current value.
Calling a BST walk O(log n) unconditionally ignores skewed trees. State O(h), with the balance assumptions separately.
Claiming that each step discards half the nodes assumes a balanced tree; BST ordering guarantees a valid subtree choice, not its size.
In the general path search, omitting exit frames leaves failed branches in the path; scheduling right before left on a LIFO stack makes the intended left-first order.
Recursive general DFS may overflow on the permitted 100,000-node chain; use explicit frames as shown.
The guarantee that both original target nodes exist is essential. If targets could be absent, the split test alone would not prove an ancestor exists; validate membership under that different contract.

Key Takeaway

The LCA is where two root-to-target routes stop sharing a prefix. A general tree needs path discovery and backtracking; BST ordering identifies the shared route using two value comparisons per node. Preserve the invariant that the chosen subtree contains both targets, then stop when no proper descendant can do so.