Lowest Common Ancestor of a Binary Search Tree
Medium · Trees · Tree · Depth-First Search · Binary Search Tree · Binary Tree
Problem
Given a binary search tree and two different values p and q that are both in it, return their lowest common ancestor: the deepest node that has both of them in its subtree. A node counts as part of its own subtree, so when p is an ancestor of q, the answer is p itself.
The search-tree order does all the work. While p and q are both smaller than the current node, both are in its left subtree; while both are larger, both are in its right subtree. The first node where they split — one on each side, or one of them equal to the node — is the answer, and nothing off that one path ever needs to be looked at.
Your lowestCommonAncestor receives the root and the two nodes, and returns a node. The tests call it through a helper that builds the tree from its level-order list, finds the nodes holding p and q, and reports the value of the node you return:
Trees here are at most 500 levels deep.
Examples
Input: root = [6,2,8,0,4,7,9,None,None,3,5], p = 2, q = 8 Output: 6
2 is smaller than 6 and 8 is larger, so they split right at the root.
Input: root = [6,2,8,0,4,7,9,None,None,3,5], p = 2, q = 4 Output: 2
Both are smaller than 6, so go left to 2. That node is p itself, and 4 is below it, so 2 is the answer.
Constraints
- 2 <= number of nodes <= 10^5
- -10^9 <= Node.val <= 10^9, and the values are distinct
- p != q, and both values are in the tree
- the tree is a valid binary search tree
- the tree is at most 500 levels deep (LeetCode allows a 10^5-node chain; tightened so recursion fits in the browser)
Approaches
- General binary-tree LCA, ignoring the order — time O(n), space O(h)
Related problems
Start free on Cariara · Coding problems · System design studio
