Problem overview
The method lowestCommonAncestor receives the root of a binary search tree and two values, p and q, that both exist in the tree. It returns the value of their lowest common ancestor: the deepest node that has both of them in its subtree. A node counts as its own ancestor, and p and q may be equal.
Take the tree with root 6, children 2 and 8, then 0 and 4 under 2, 7 and 9 under 8, and 3 and 5 under 4.
- For
p = 2,q = 8the answer is 6: one value is in the left subtree and the other in the right one, so no deeper node holds both. - For
p = 2,q = 4the answer is 2, because 4 is below 2 and 2 is its own ancestor. - For
p = 5,q = 3the answer is 4, their shared parent.
The follow-up asks for O(h) time, where h is the height of the tree, with O(1) extra space.
Approach: let the values choose the direction
For a general binary tree you would have to search both subtrees, because nothing tells you where a value is. A BST does tell you: every value smaller than a node is in its left subtree, and every larger value is in its right subtree.
The root is above everything, so it is a common ancestor of p and q. The question is whether a lower one exists. Look at the current node and compare it with both values:
- If both values are smaller than the node, both are in its left subtree, and so is their lowest common ancestor. Move left.
- If both are larger, move right for the same reason.
- Otherwise the two values can't both be on one side. Either one is smaller and the other larger, or one of them equals the node's value. In both cases this node has both below it or at it, and moving to either child would leave one of them behind. This node is the answer.
Each pass goes one level down and never goes back, so the walk takes at most h passes. It needs no recursion and no stack, only the pointer to the current node.
On the example with p = 5 and q = 3: at 6 both values are smaller, so move to 2. At 2 both are larger, so move to 4. At 4, 5 is larger and 3 is smaller, so the walk stops and returns 4.
Step by step
- Declare
nodewithletand set it toroot. It is the pointer that moves down the tree, so it can't be aconst. - Write a
while (node)loop. A missing child isnull, which is falsy, so the loop ends if the walk ever falls off the tree. Each pass handles one node. - If both values are smaller than
node.val, move tonode.left. The two checks are joined with&&: moving left is only safe when both values are smaller. - Otherwise, if both are larger, move to
node.right. This is the mirror image of the previous step. - In the final
else, returnnode.val. This branch covers a split between the two sides and also the case whereporqequals the node's value. - After the loop, return -1. Because
pandqare in the tree, the loop always returns first. The line only guarantees that the method returns a number on every path.
The solution in JavaScript
class Solution {
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 -1;
}
}Some details about JavaScript:
pandqare plain numbers, not nodes. The comparisons are numeric (p < node.val), and the method returnsnode.val, a number.while (node)relies on truthiness. A tree node is an object, which is always truthy, andnullis falsy, so the loop runs exactly whilenodepoints at a real node. Node values don't matter here: a node holding 0 is still an object and still truthy.- The test for "both smaller" must come with
&&, not||. With||, a node that splits the two values would be skipped.
Complexity
Time is O(h): each pass moves one level down, so there are at most h passes with constant work in each. For a balanced tree that is about log n passes, and for a tree that is a single chain of n nodes it is n. Extra space is O(1), since the method only keeps the pointer node.
Edge cases and common mistakes
- One value is an ancestor of the other. The walk stops at the ancestor, because that node's value is neither smaller nor larger than itself. With
p = 2andq = 4the answer is 2. pequalsq. The walk heads down to the node holding that value and returns it. Withp = q = 7the answer is 7.- A single-node tree. The first pass reaches the else branch and returns the root's value.
- Using
<=or>=in the two checks. That would send the walk past a node that equalsporq, which is the answer. - Searching the whole tree. A full traversal works but costs
O(n)and ignores the BST ordering.
Testing
On the example tree, lowestCommonAncestor(root, 2, 8) returns 6, (root, 2, 4) returns 2, (root, 5, 3) returns 4, (root, 7, 7) returns 7 and (root, 3, 9) returns 6.
