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, so if p is above q, the answer is p. The two values can also 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 and q = 8 the answer is 6: they lie on different sides of the root. For p = 2 and q = 4 the answer is 2, since 4 sits inside the subtree of 2. For p = 5 and q = 3 the answer is 4, the parent of both.
The follow-up asks for O(h) time, where h is the height of the tree, and O(1) extra space.
Approach: walk down and stop where the paths split
In a general binary tree, finding a common ancestor means searching both subtrees. A BST makes it easier, because every value in a node's left subtree is smaller than the node and every value in its right subtree is larger. Comparing p and q with the current node's value tells you where each of them lies.
- If both are smaller than the node, both are in the left subtree, so the lowest common ancestor is there too. Go left.
- If both are larger, go right.
- Otherwise they are on different sides of the node, or one of them is the node itself. Moving down in either direction would leave one of them behind, so this node is the deepest one that has both below it (or at it). That is the answer.
The walk starts at the root, which is always a common ancestor, and each step moves one level down while the answer stays inside the current subtree. It needs no recursion and no stack, so extra space is constant.
On the example with p = 5 and q = 3: at 6, both values are smaller, so go left to 2. Both are larger than 2, so go right to 4. At 4, 5 is larger and 3 is smaller, so the paths split, and the answer is 4.
Step by step
- Start a walker at the root. A
TreeNodevariable namednodewill move down the tree. - Loop while
node != null. Each pass looks at one node and either returns or moves one level down. - Both values smaller: if
p < node.val && q < node.val, setnode = node.left. - Both values larger: with an
else if, setnode = node.rightwhenpandqare both greater thannode.val. - Otherwise return
node.val. The values split here, or one equalsnode.val. This also covers the rule that a node is its own ancestor. - Return -1 after the loop. Because
pandqare in the tree, the loop always returns first. Java still requires every path of a method that returns anintto end in a return.
The solution in Java
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;
}
}
Java details worth a closer look:
pandqare plainintvalues, not nodes, so they are compared with<and>directly. Had they beenIntegerobjects,==would compare references, but ordering comparisons would still unbox them.- The method returns
node.val, anint, rather than the node. The tree is only read, never changed. - The final
return -1is there for the compiler. Without it, the code would fail to compile with a "missing return statement" error, because the compiler can't prove the loop returns. - The three branches cover every case. The last
elsecovers every case where the first two conditions are false: the values straddle the node, or at least one equalsnode.val.
Complexity
Time: O(h). Each pass of the loop moves one level down, so the loop runs at most h times, where h is the height of the tree. For a balanced tree that is O(log n), and for a tree that is a single chain it is O(n).
Space: O(1). The only extra storage is the variable node. A recursive version would use O(h) stack space for the same walk.
Edge cases and common mistakes
- One value is an ancestor of the other. For
p = 2andq = 4, the walk reaches 2, wherepis not smaller than the node, so neither of the first two conditions holds and 2 is returned. Using<=and>=in the first two conditions would walk past the answer. pequalsq. Forp = q = 7the walk goes right at 6, reaches 8 and goes left, and stops at 7, which is returned.- A single-node tree. Both values must equal the root's value, so the root is returned.
- Treating it as a general tree. Searching both subtrees for
pandqworks but ignores the BST property and costsO(n). - Assuming
p < q. The tests can give the values in either order. The conditions test both values against the node, so order doesn't matter.
Testing
With the example tree [6,2,8,0,4,7,9,null,null,3,5]:
p = 2,q = 8gives6.p = 2,q = 4gives2.p = 5,q = 3gives4.p = 7,q = 7gives7.p = 3,q = 9gives6.
