Lowest Common Ancestor of a BST
A database index is a binary search tree with distinct keys. To answer a range query between two keys p and q, the engine first finds the node where the search paths to p and q part ways: their lowest common ancestor, the deepest node whose subtree contains both keys. Every key between p and q lives somewhere below that node.
Given the root and two different keys p and q that are both in the tree, return the value of their lowest common ancestor. A node counts as its own ancestor, so if q lies in the subtree of p, the answer is p.
Adapted for this site: instead of node references, p and q are plain key values, and you return the ancestor's value as an integer.
Input: root = [40,20,60,10,30,50,70,null,15,25], p = 15, q = 25 Output: 20
Explanation: The search for 15 turns left at 20 and the search for 25 turns right there, so their paths split at 20.
Input: root = [40,20,60,10,30,50,70,null,15,25], p = 25, q = 70 Output: 40
Explanation: The paths split right away: 25 is left of the root and 70 is right of it.
Input: root = [40,20,60,10,30,50,70,null,15,25], p = 30, q = 25 Output: 30
Explanation: 25 is the left child of 30, and a node is its own ancestor.
Constraints
- The tree has between 2 and 10^5 nodes.
- Keys are distinct and fit in a 32-bit signed integer.
pandqare different, and both occur in the tree.
💡 Hint 1
In a general binary tree you would have to search both subtrees. What does the BST ordering tell you about where p and q are?
💡 Hint 2
If both values are smaller than the current node, the LCA is in the left subtree; if both are larger, it is in the right subtree.
💡 Hint 3
The first node where p and q fall on different sides (or one of them equals the node) is the answer. No recursion is needed.
Try it yourself first ✎
Solutions stick better after a real attempt. Peek when you're ready.
Approach
Use the BST ordering to walk down a single path from the root. If both p and q are smaller than the current value, the LCA must be in the left subtree; if both are larger, it is in the right subtree. Otherwise the two values split here (or one of them is this node), so this node is the lowest one above both. Return its value.
function lowestCommonAncestor(root, p, q) {
let 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 null;
}class Solution {
public 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;
}
}No submissions yet. Press Submit to run your code against every test.
/**
* Definition for a binary tree node (provided):
* function TreeNode(val, left, right) { this.val = val ?? 0; this.left = left ?? null; this.right = right ?? null; }
*
* @param {TreeNode} root
* @param {number} p
* @param {number} q
* @return {number} the value of the lowest common ancestor
*/
function lowestCommonAncestor(root, p, q) {
}Run your code to see results here.