Problem overview
The method lowestCommonAncestor receives the root of a binary search tree (a TreeNode?) 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.
The tree in the examples has root 6, with 2 and 8 below it; 2 has the children 0 and 4, 8 has 7 and 9, and 4 has 3 and 5. For p = 2 and q = 8 the answer is 6, since the two sit on different sides of the root. For p = 2 and q = 4 the answer is 2: 4 is inside the subtree of 2, and 2 is its own ancestor. For p = 5 and q = 3 the answer is 4, their parent.
Approach: let the values choose the direction
In a general binary tree you would have to search both subtrees for the two values. A binary search tree orders its values: everything in a node's left subtree is smaller than the node, everything in its right subtree is larger. So at any node you can tell where p and q live by comparing them with the node's value.
Start at the root, which is above every node and so is always a common ancestor. Then ask one question at each node:
- Both values are smaller than the node: both are in the left subtree, so the lowest common ancestor is there too. Move left.
- Both are larger: move right.
- Otherwise, they are on different sides, or one of them equals the node. Going down either way would leave one value behind, so this node is the answer.
For p = 5 and q = 3: at 6, both are smaller, so go left to 2. At 2, both are larger, so go right to 4. At 4, 3 is smaller and 5 is larger, so they split here: the answer is 4. Each step goes one level down, so the walk takes at most as many steps as the tree is tall, with no recursion and no extra memory.
Step by step
- Declare
nodewithvarand set it toroot. It is aTreeNode?because it becomesnilwhen you step past a leaf. - Loop with
while let current = node. It repeats whilenodeisn'tnil, and each time binds the unwrapped node tocurrent. - Both smaller: if
p < current.val && q < current.val, setnodetocurrent.left. - Both larger: with
else if, setnodetocurrent.right. - Otherwise return
current.val. The values are on different sides or one of them is this node's value, so this node is the deepest one with both below it. - Return -1 after the loop. Because
pandqare in the tree, the loop always returns before it ends. Swift needs a return on every path of a function that returns anInt.
The solution in Swift
class Solution {
func lowestCommonAncestor(_ root: TreeNode?, _ p: Int, _ q: Int) -> Int {
var node = root
while let current = node {
if p < current.val && q < current.val {
node = current.left
} else if p > current.val && q > current.val {
node = current.right
} else {
return current.val
}
}
return -1
}
}
Swift details worth knowing:
while let. It combines a loop with optional binding:while let current = noderuns its body only whennodeholds a value, and inside the bodycurrentis a plainTreeNode. No!is needed.- Optional children.
current.leftandcurrent.rightareTreeNode?, the same type asnode, so they can be assigned to it directly. - Type inference.
var node = rootgets the typeTreeNode?fromroot, so the loop can assignnilchildren to it. - Classes are references.
TreeNodeis a class, sonode = current.leftonly moves the reference. The tree is never changed. - The return type is
Int, so the method returns the value of the node,current.val, not the node.
Complexity
Time: O(h), where h is the height of the tree. Each pass goes one level down and does constant work. For a balanced tree that is O(log n); for a tree that is a single chain it is O(n).
Space: O(1). Only node and current are kept. A recursive version would use O(h) stack space.
Edge cases and common mistakes
- One value is the ancestor. For
p = 2andq = 4, at node 2 neither "both smaller" nor "both larger" holds, sincepequals the node's value, so the walk stops and returns 2. - Equal values.
p = q = 4returns 4: the walk goes 6, 2, 4 and stops at the node that holds the value. - A single-node tree. With root 5 and
p = q = 5the answer is 5. - Using
<=and>=in the first two branches. That would move past a node that equalsporq, losing the case where a value is its own ancestor. The comparisons must be strict. - Joining with
||instead of&&. "Either value smaller" doesn't put both in the left subtree. - Searching the whole tree. The ordering of the BST makes it unnecessary, and it would raise the cost from
O(h)toO(n). - Splitting at the wrong level. For
p = 0andq = 5, the walk goes 6, then 2, where 0 is smaller and 5 is larger. The answer is 2, not 6.
Testing
- Root 6 tree,
(2, 8)gives 6. (2, 4)gives 2.(5, 3)and(3, 5)give 4.(4, 4)gives 4, and(0, 9)gives 6.(7, 9)gives 8, and(0, 5)gives 2.
