#235 Lowest Common Ancestor of a Binary Search Tree
frequently reported atLinkedInMetaBloombergAmazonMicrosoftGoogle
the problem
In plain words
Given a BST and two different nodes p and q in it, return their lowest common ancestor (a node may be its own ancestor).
in root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
out 6
in root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
out 2
- 2 ≤ number of nodes ≤ 10⁵
- -10⁹ ≤ Node.val ≤ 10⁹
- Values unique, p ≠ q, both in the tree
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternBST property
While p and q are both smaller (or both larger) than the current node, the LCA is on that side. The first node where they split — or that equals one of them — is the LCA.
solutions
From brute force to optimal
Use LC 236's recursion, ignoring the BST order.
- Return root if null, p or q.
- Recurse both sides; if both non-null, root is the LCA.
May explore the whole tree.
Recursion stack.
class Solution { /** The binary-tree LCA from the previous chapter: correct, but ignores the ordering. */ public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null || root == p || root == q) return root; TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); if (left != null && right != null) return root; return left != null ? left : right; }}Go left if both are smaller, right if both are larger, otherwise stop.
- Both < root → recurse left.
- Both > root → recurse right.
- Else return root.
One path down.
Recursion stack.
class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (p.val < root.val && q.val < root.val) return lowestCommonAncestor(root.left, p, q); if (p.val > root.val && q.val > root.val) return lowestCommonAncestor(root.right, p, q); return root; // they split here (or root is one of them) }}The same walk with a pointer.
- cur = root.
- Move left/right while both values are on the same side.
- Return cur.
One path down.
One pointer.
class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { TreeNode cur = root; while (true) { if (p.val < cur.val && q.val < cur.val) cur = cur.left; // both smaller else if (p.val > cur.val && q.val > cur.val) cur = cur.right; // both larger else return cur; // they split here } }}Dry run
in the room
How to say it in the interview
talk track
- Contrast with LC 236: the order tells us which way to go, so we never need to search both sides.
traps
- Comparing
p.val < root.val || q.val < root.val(or) instead of both — that walks past the split.
what they ask next
Follow-ups
What if it's a plain binary tree, not a BST (LC 236)?
The order no longer tells you a side. Recurse into both children: if both return a node, the current node is the LCA; otherwise pass up the non-null one. O(n) time, O(h) space.
What if p or q might not be in the tree?
The walk alone can't tell. First search the BST for both values (O(h) each); if either is missing, return null.
before you submit
Edge cases to test
- p is an ancestor of q → p itself is the LCA.
- p and q on opposite sides of the root → the root.
- Values up to ±10⁹ → compare them, never subtract them, so nothing overflows.
practise next
Similar problems
- #236Lowest Common Ancestor of a Binary TreeMediumin Tree Recursion
- #700Search in a Binary Search TreeEasyin BST
- #285Inorder Successor in BSTMediumin BSTLeetCode Premium