Problem overview
The function lowestCommonAncestor receives the root of a binary search tree and two values, p and q, that are both in the tree. It returns the value of their lowest common ancestor: the deepest node that has both values in its subtree. A node counts as its own ancestor, and p and q may be equal.
In the tree with root 6, children 2 and 8, and 2 having children 0 and 4 (4 having children 3 and 5), the answers are:
p = 2, q = 8gives 6: they sit on different sides of the root.p = 2, q = 4gives 2: 4 is inside the subtree of 2, and a node is its own ancestor.p = 5, q = 3gives 4: they are the two children of 4.
The follow-up asks for O(h) time, where h is the height of the tree, and O(1) extra space. This lesson does exactly that.
Approach: let the values choose the direction
For a general binary tree you would have to search for both nodes. A BST gives more: everything smaller than a node's value is in its left subtree, and everything larger is in its right subtree. Start at the root, which is above everything and so is a common ancestor, and look for the lowest one:
- If both
pandqare smaller than the current value, they are both in the left subtree, and so is their lowest common ancestor. Go left. - If both are larger, go right.
- Otherwise they are split: one is on each side, or one of them equals the current value. Going down either way would leave a value behind, so this node is the answer.
Take p = 5, q = 3. At 6 both are smaller, so go to 2. At 2 both are larger, so go to 4. At 4, 5 is larger and 3 is smaller, so the values are split and the answer is 4.
Each pass moves one level down, so the walk makes at most h passes. A recursive version would use O(h) stack space; a loop that only moves a pointer uses none.
Step by step
- Start a pointer at the root.
nodeis the node we are looking at; the root is a common ancestor, so we are never above the answer. - Loop while
nodeis not null. Each pass either returns or moves down one level. - Both values smaller: join the two comparisons with
&&and movenodetonode->left. - Both values larger: the mirrored case, in an
else if, moves tonode->right. - Anything else: the values are on different sides, or one equals the node's value. Return
node->val. - Return -1 after the loop. Because
pandqare in the tree, the loop always returns first. The line only gives the function a return value on every path.
The solution in C++
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;
}
};
The C++ details worth a closer look:
- Values, not nodes.
pandqare plainintvalues, so they are compared directly withnode->val. Nothing needs to be dereferenced. NULLin the loop condition. A pointer is compared withNULLhere, as in the lesson'sTreeNodedefinition.nullptris the modern spelling and works the same way.- Only a pointer moves.
node = node->leftchanges the local pointer. It doesn't modify the tree and allocates nothing. - The final
return -1. A non-void function that can reach its end without areturnhas undefined behaviour in C++ if that path is taken, and compilers warn about it. The extra line is dead code here, but it keeps the function well-formed. The value -1 is safe as a marker only because it's unreachable; node values can be negative too.
Complexity
Time: O(h). Every pass descends one level and the loop ends at the latest at the node where the paths to p and q split. For a balanced tree that is O(log n); for a tree that is a single chain it is O(n).
Space: O(1). One pointer and no recursion.
Edge cases and common mistakes
- One value is an ancestor of the other. For
p = 2, q = 4, at node 2 the checkp < 2fails, and so doesp > 2, so the code returns 2. Using<=or>=in the first two branches would walk past the answer. - Equal values.
p = q = 3walks down to the node 3 and returns 3. - A single-node tree. The root is returned immediately.
- Assuming the answer is always in the middle. It can be the root, one of the two values, or any node between them.
- Using the BST property on the wrong tree. The direction rule relies on the ordering. In an unordered binary tree, comparing values says nothing about which subtree they are in.
- Mixing up the two checks. Joining them with
||would turn when only one value is smaller into a move left, which can lose the other value.
Testing
On the tree [6,2,8,0,4,7,9,NULL,NULL,3,5]:
p = 2, q = 8gives 6.p = 2, q = 4gives 2.p = 5, q = 3gives 4.p = 3, q = 3gives 3.p = 0, q = 5gives 2.
