arcbjorn

thoughtbook

Saturday, March 4, 2023

Lowest common ancestor of a binary tree

Leetcode 236 problem.

Go

  • Time complexity: O(n)O(n) - n is a number of nodes
  • Auxiliary space: O(h)O(h) - 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
}
Creative Commons Licence