Lowest Common Ancestor of a Binary Search Tree
- 1 min read
- DFS
- BFS
- Tree
- Blind75
- LC-Medium
- Binary Tree
- Binary Search Tree
3 years ago
Approach: Check where split occurs
- The common ancestor of two nodes is the point at which a split in the tree happens.
- There are only two cases where a split doesn't happen:
- When both
pandqare in the right subtree - When both
pandqare in the left subtree
- When both
- If the above two conditions occur, go down to the appropriate subtree
- If not, return
cur, which will be the LCA
def lowestCommonAncestor(root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
cur = root
while cur:
if cur.val < p.val and cur.val < q.val:
cur = cur.right
elif cur.val > p.val and cur.val > q.val:
cur = cur.left
else:
return cur