Saturday, March 4, 2023
Lowest common ancestor of a binary tree
Go
- Time complexity: -
n
is a number of nodes - Auxiliary space: -
h
is a height of a binary tree
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
if root == p || root == q || root == nil {
return root
}
left := lowestCommonAncestor(root.Left, p, q)
right := lowestCommonAncestor(root.Right, p, q)
if left == nil && right == nil {
return nil
}
if left != nil && right != nil {
return root
}
if (left != nil) {
return left
}
return right
}