Problem overview
The method LowestCommonAncestor receives the root of a binary search tree of TreeNode objects and two integers p and q, both values stored in the tree. It returns the value of their lowest common ancestor: the deepest node that has both p and q in its subtree. A node counts as its own ancestor, and p and q may be equal.
In a binary search tree, every value in a node's left subtree is smaller than the node, and every value in its right subtree is larger. 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 = 2andq = 8the answer is 6: they are on opposite sides of the root. - For
p = 2andq = 4the answer is 2, because 4 is below the node 2 and the node 2 is its own ancestor. - For
p = 5andq = 3the answer is 4: its two children are 3 and 5.
Approach: follow the values down until the paths split
Any ordinary tree would need a search of both subtrees. The BST ordering makes that unnecessary, because comparing a value with a node tells exactly which subtree holds it.
Start at the root, which is above every node and so is a common ancestor. Then look at the current node:
- If both
pandqare smaller than the node's value, both are in its left subtree, and so is their lowest common ancestor. Move left. - If both are larger, move right.
- Otherwise the two values are on different sides of the node, or one of them is the node's own value. Going into either child would leave one of the values outside, so this node is the lowest one that has both below it.
Because the walk stops at the first node where the values do not both go the same way, it finds the deepest such node. It needs no recursion and no list of ancestors.
For p = 5 and q = 3 in the tree above: at 6, both 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 answer is 4.
Step by step
- Start with
node = root. It is the current position in the walk. - Loop while
node != null. Each pass looks at one node and either returns or goes one level down. - Both values smaller. If
p < node.val && q < node.val, setnode = node.left. - Both values larger. With
else if, ifp > node.val && q > node.val, setnode = node.right. - Anything else. In the
elsebranch, returnnode.val. The values are split by this node, or one of them equals it. - Return -1 after the loop. The loop always returns first, since
pandqare in the tree. The line is there because C# requires anintmethod to return a 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 knowing:
pandqare plainints, not nodes. They are compared directly withnode.val. There is no need to look nodes up first.- The compiler checks every path. C# rejects a method with a return type if some path reaches the end without returning (error CS0161, "not all code paths return a value"). It can't prove that the loop always returns, so the final
return -1;is required, even though it never runs on valid input. - Reassigning
nodedoesn't change the tree.nodeis a local reference. Moving it tonode.leftchanges where the variable points, not any node.
Complexity
Let h be the height of the tree.
Time: O(h). Each pass moves one level down, so there are at most h passes. For a balanced tree that is about log n. For a tree that is a single chain, it is n.
Space: O(1). The only extra memory is the variable node. A recursive version does the same moves but uses up to h stack frames, so the loop is the better choice for the follow-up.
Edge cases and common mistakes
- One value is an ancestor of the other. For
p = 2andq = 4in the example, at the node 2 the valuepequalsnode.val, so neither check passes and the method returns 2. This is why the first two conditions use strict comparisons. - Equal values. With
p == q, such as3and3, the walk goes down to the node 3 and returns 3. Withp = q = 6it returns 6 at once. - A one-node tree. With root 1 and
p = q = 1, the method returns 1. - The order of
pandq. It makes no difference:(5, 3)and(3, 5)give the same answer, since both conditions treat the two values the same way. - The values on the two extremes. For
p = 0andq = 9the answer is the root, 6. - Using
<=or>=. The walk would continue past a node that equalsporqand could skip the right answer. - Using
||instead of&&. The walk would go down as soon as one value points that way, and leave the other one behind. - Searching both subtrees. That solves the problem for any binary tree, but it ignores the ordering and costs
O(n).
Testing
With the 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 = 3,q = 3gives3.p = 0,q = 5gives2.p = 7,q = 9gives8.p = 0,q = 9gives6.
