Description
Find the lowest node whose subtree contains two given nodes in a BST with unique values. Both nodes exist; example arguments identify them by value.
Solution
def lowest_common_ancestor(root, p, q):
while root:
if max(p.val, q.val) < root.val:
root = root.left
elif min(p.val, q.val) > root.val:
root = root.right
else:
return rootExamples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[4,2,6,1,3],1,3]- Output
2
Targets 1 and 3 split at 2.
Example 2
- Input
[[4,2,6],2,6]- Output
4
The targets lie on opposite sides of 4.
Example 3
- Input
[[2,1],2,1]- Output
2
A target can be its own ancestor.
Approach
Walk left if both targets are smaller, right if both are larger, otherwise the current node is the split point.
Time & space
O(h) time; O(1) space. Here n is the node count, and h is the tree height.