Problem overview
The function lowest_common_ancestor receives the root of a binary search tree, as an Option<Box<TreeNode>>, and two values p and q that are 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.
Use the tree [6, 2, 8, 0, 4, 7, 9, None, None, 3, 5]. For p = 2 and q = 8 the answer is 6, because 2 sits in the left subtree of 6 and 8 in the right one, and 6 is the deepest node with both below it. For p = 2 and q = 4 the answer is 2: 4 is in the subtree of 2, and 2 is its own ancestor. For p = 5 and q = 3 the answer is 4, their common parent.
Approach: let the values choose the direction
For an ordinary binary tree you would have to search both subtrees. A binary search tree gives much more information: everything in a node's left subtree is smaller than the node, and everything in its right subtree is larger. So at any node, comparing p and q with its value tells you where they are without looking.
Start at the root, which is always a common ancestor. Then at each node there are three cases:
- Both values are smaller than the node. They are both in the left subtree, so the lowest common ancestor is there too. Move left.
- Both values are larger. Mirror image: move right.
- Otherwise the values are on different sides of the node, or one of them equals the node's value. Going down either way would leave one value behind, so this node is the answer.
Trace p = 5, q = 3. At 6 both are smaller, so go left to 2. At 2 both are larger, so go right to 4. At 4, 5 is larger and 3 is smaller, so 4 is the answer.
Each step moves one level down, so the walk takes at most as many steps as the tree is tall, O(h). It needs no stack and no recursion, which meets the follow-up's O(1) space goal.
Step by step
- Create the cursor.
nodeis a mutable variable holdingroot.as_deref(). The method turnsOption<Box<TreeNode>>intoOption<&TreeNode>, a borrowed view of the nodes, so you can walk the tree without moving anything out of it. - Loop while there is a node.
while let Some(current) = noderuns the body withcurrentbound to the node and ends whennodebecomesNone. - Go left when both
pandqare smaller thancurrent.val, by settingnodetocurrent.left.as_deref(). - Go right in the mirrored case, with an
else if. - Otherwise return
current.val. The two values are split by this node, or one of them is this node, and areturnis needed because it leaves the function from inside the loop. - Add a tail value. After the loop,
-1without a semicolon gives the function a value on every path. It is never reached, becausepandqare in the tree and the loop always returns first.
The solution in Rust
impl Solution {
fn lowest_common_ancestor(root: Option<Box<TreeNode>>, p: i32, q: i32) -> i32 {
let mut node = root.as_deref();
while let Some(current) = node {
if p < current.val && q < current.val {
node = current.left.as_deref();
} else if p > current.val && q > current.val {
node = current.right.as_deref();
} else {
return current.val;
}
}
-1
}
}
Rust details worth noticing:
- Borrowing, not moving.
rootis taken by value, butas_deref()only borrows from it, sonodeandcurrentare references into the tree. Nothing is cloned and nothing is dropped early. - Reassigning a copy of the cursor.
Option<&TreeNode>isCopybecause shared references are, sowhile let Some(current) = nodedoesn't consumenode, and the assignments inside the loop are fine. - Why
.as_deref()on the children.current.lefthas typeOption<Box<TreeNode>>. Writingnode = current.leftfails with a mismatched-types error: expectedOption<&TreeNode>, foundOption<Box<TreeNode>>.as_deref()gives the typenodealready has. - The final expression. A line without a semicolon at the end of the function body is its return value. A
returnwith a semicolon is only for leaving early.
Complexity
Time: O(h), where h is the height of the tree. Each loop pass goes one level down and does two comparisons. For a balanced tree that is about log n steps, and for a tree that is a single chain it is n.
Space: O(1). The only extra memory is the node reference and the arguments. A recursive version would use O(h) stack space.
Edge cases and common mistakes
- One value is an ancestor of the other. For
p = 2andq = 4, the walk reaches 2 and finds 2 is not larger than itself, and 4 is not smaller. Neither move applies, and it returns 2. - Equal values. For
p = 3andq = 3the answer is 3, the node itself: at every node on the way down both values are on the same side, until the walk reaches 3. - A single node. The root is the answer for every valid pair.
- Using
<=instead of<. If you testp <= current.val, you move away from a node that equalspand lose the case where the ancestor is one of the two values. - Treating it as a general binary tree. Searching both subtrees works but takes
O(n)time. The ordering of a BST makes that unnecessary. - Mixing up the sides. Smaller values go left and larger values go right. Swapping them walks away from both targets.
Testing
On the tree [6, 2, 8, 0, 4, 7, 9, None, None, 3, 5]:
p = 2,q = 8gives6.p = 2,q = 4gives2.p = 5,q = 3gives4.p = 3,q = 3gives3.p = 6,q = 9gives6.
