Lowest Common Ancestor
- 2 min read
- LC-Medium
- Binary-search-tree
3 years ago
Solution
- Also look at Lowest Common Ancestor of a Binary Tree
- The lowest common ancestor of two nodes is wherever a split occurs, i.e. the point in the tree where one value is in the left and one value is in the right
- The other cases are when both values are in the left subtree or both values are in the right subtree
- When this happens, we need to recur down left or right
- When either of these conditions (i.e. both values are not in the same subtree) is met, we can immediately return because one of two things happen:
- We are at a unique LCA (i.e. the ancestor is not equal to p or q)
- We are either at p or q, and one or the other is either in the right or left subtree
- Since this is our exit condition and we've found our LCA, we return current
- Since the solution is guaranteed to exist, we don't need to do any other validation and can simply return
| Time | Space | Explanation |
|---|---|---|
O(log n) or O(h) | O(1) |
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
cur = root
while cur:
if p.val < cur.val and q.val < cur.val:
cur = cur.left
elif p.val > cur.val and q.val > cur.val:
cur = cur.right
else:
return cur