Practice Lowest Common Ancestor of a Binary Search Tree
Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.
Lowest Common Ancestor of a Binary Search Tree
Problem Statement
Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST. According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Source: Lowest Common Ancestor of a Binary Search Tree on LeetCode. Use the original task for its coding environment and submissions.
Examples
# Example 1
root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
6
# Example 2
root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
2
# Example 3
root = [2,1], p = 2, q = 1
2
Constraints
How to solve Lowest Common Ancestor of a Binary Search Tree
Original notes for interview preparation, written for this problem. Reviewed .
Key insight
The search property tells you where to go: if both targets are smaller than the current node the LCA is in the left subtree, if both are larger it is in the right, and the first node where they split, or that equals one of them, is the answer.
Why brute force is not enough
Treating the tree as a generic binary tree and recursing into both subtrees to locate each target is O(n), visiting nodes the ordering already rules out; with up to 10^5 nodes it passes but shows you missed the property that makes this easier than the general problem.
Approach
- Start at the root with the two target values; the invariant is that both targets lie in the subtree rooted at the current node.
- If both values are less than the current value, move to the left child; the invariant holds because the whole right subtree exceeds both.
- If both are greater, move to the right child by the symmetric argument.
- Otherwise the targets straddle the current node or one equals it, so no deeper node contains both; return the current node.
- The walk follows a single root-to-node path, so a loop with one pointer suffices.
Walkthrough of Example 2
root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 → 2
- Begin at the root 6 with targets 2 and 4; both are smaller, so move to the left child 2.
- At node 2, one target equals the node and the other, 4, is greater, so the targets are not both on one side.
- Stop and return node 2, matching the expected output; a node counts as its own ancestor, so p being the LCA is allowed.
- As a check, 4 sits in the right subtree of 2, so 2 is indeed the lowest node whose subtree holds both.
Time and space
Time O(h) · Space O(1). h is the tree height, O(log n) when balanced and O(n) when skewed; the iterative walk keeps only the current pointer.
Interview pitfalls
- Using strict inequalities for both directions and never handling equality, which can walk past a node that is itself p or q, as example 2 shows.
- Assuming p is smaller than q; the comparisons must work in either order, so compare each value independently or normalize first.
- Mixing up node references and values; be explicit about whether p and q are nodes or integers.
- Values reach plus or minus 10^9, so avoid intermediate arithmetic such as sums or midpoints that could overflow 32 bits.
- Falling back to the general-tree recursion that visits both subtrees; correct but O(n) and a missed insight.
Follow-up questions interviewers ask
- How would you solve LCA in an arbitrary binary tree without the search property?
- If every node has a parent pointer, can you find the LCA without the root?
- How would you answer many LCA queries on a static tree quickly?
Further reading on the technique: Lowest common ancestor
Related LeetCode Problems
Practice more problems similar to Lowest Common Ancestor of a Binary Search Tree.
Review your practice with PhantomCodeAI
After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.