Lowest Common Ancestor of a Binary Search Tree — Solution
Lowest Common Ancestor of a Binary Search Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Lowest Common Ancestor of a Binary Search Tree is a medium coding problem on depth-first search, binary search and trees, asked in Amazon, Microsoft, Meta and LinkedIn interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Binary Search, Trees
- Asked at: Amazon, Microsoft, Meta, LinkedIn
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given the root of a binary search tree with distinct values and the values p and q of two different nodes in it.
The lowest common ancestor of two nodes is the deepest node that has both of them in its subtree — where a node counts as being in its own subtree, so a node can be the ancestor of itself. Return the value of the lowest common ancestor of the nodes holding p and q.
Example 1
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: 2 is in the root's left subtree and 8 in its right, so they part ways at the root 6.
Example 2
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: 4 lies below 2, and a node counts as its own descendant, so the answer is 2.
Example 3
Input: root = [2,1], p = 2, q = 1
Output: 2
Explanation: The root is an ancestor of 1 and of itself.
Constraints
2 <= number of nodes <= 10^5-10^9 <= Node.val <= 10^9all node values are distinctroot is a valid binary search treep != qp and q both exist in the tree
Hints for Lowest Common Ancestor of a Binary Search Tree
Hint 1
Compare
pandqwith the root's value: when both are smaller, both nodes are in the left subtree; when both are larger, both are in the right subtree.Hint 2
Keep moving down while
pandqare on the same side of the current node.Hint 3
The first node where they split — or where one of them equals the node — is the answer.
How to solve Lowest Common Ancestor of a Binary Search Tree
The ordering tells you which side each value is on, so walk down from the root while p and q lie on the same side; the node where they separate is their lowest common ancestor.
Approach
- Start at the root.
- If
pandqare both smaller than the node's value, move to the left child. - If both are larger, move to the right child.
- Otherwise (they are on different sides, or one equals the node) return the node's value.
Why it works
While both values lie on the same side of a node, both nodes are in that child's subtree, so the child is a common ancestor deeper than the current one. At the first node where they do not, one is in its left subtree (or is the node) and the other in its right subtree (or is the node), so no child contains both — this node is the deepest common ancestor.
Complexity
- Time —
O(h), h the height of the tree - Space —
O(1)
Pitfalls
- A node is its own descendant: when
pis the current node, it is the answer even thoughqis below it. - The general binary-tree method also works but ignores the ordering that makes this a single walk.
Reference solution
Python
from typing import Optional
def lowestCommonAncestor(root: Optional[TreeNode], p: int, q: int) -> int:
node = root
while node:
if p < node.val and q < node.val:
node = node.left
elif p > node.val and q > node.val:
node = node.right
else:
return node.val
return -1Java
public static int lowestCommonAncestor(TreeNode root, int p, int q) {
TreeNode node = root;
while (node != null) {
if (p < node.val && q < node.val) node = node.left;
else if (p > node.val && q > node.val) node = node.right;
else return node.val;
}
return -1;
}C++
int lowestCommonAncestor(TreeNode* root, int p, int q) {
TreeNode* node = root;
while (node) {
if (p < node->val && q < node->val) node = node->left;
else if (p > node->val && q > node->val) node = node->right;
else return node->val;
}
return -1;
}JavaScript
var lowestCommonAncestor = function(root, p, q) {
var node = root;
while (node !== null) {
if (p < node.val && q < node.val) node = node.left;
else if (p > node.val && q > node.val) node = node.right;
else return node.val;
}
return -1;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Binary Search