Lowest Common Ancestor of a Binary Tree
- 2 min read
- LC-Medium
- Binary Tree
3 years ago
Solution
- Do a typical recursive Depth-first Search traversal
- If at any point the current node is null or equal to one of the input nodes, return the current node as it is.
- If the return values from both the left and right subtrees are null, code will return none (there is no explicit code for this in the solution)
- If the node value that equals one of the inputs is found in a subtree, we recur that up the call stack.
- At any point, there are 4 cases possible:
- Both left and right are null. In this case, return null.
- Left is null and right is not null. Return right
- Right is null and left is not null. Return left.
- Left and right both are not null. This means we are at our ancestor. Return root.
| Time | Space | Explanation |
|---|---|---|
O(n) | O(n) |
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if root is None or root == p or root == q:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left and right:
return root
if right: # Alternatively, condition could be written as if left is None
return right
if left: # Alternatively, condition could be written as if right is None
return left
Alternative Code (A bit more hard to understand)
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if root is None or root == p or root == q:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left and right:
return root
return left or right