Lowest Common Ancestor of a Binary Tree


#1

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given the following binary tree:  root = [3,5,1,6,2,0,8,null,null,7,4]

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself
             according to the LCA definition.

Note:

  • All of the nodes' values will be unique.
  • p and q are different and both values will exist in the binary tree.

#2

The below code uses the following algorithm.

  1. Do a level order traversal and create a map of child- node to parent-node. root's parent node would be marked as nil.
  2. Create a set of all parent nodes starting from p. (use the map created on step 1)
  3. Check if any of the q's parents exist in the set created in step 2, if it is , return that value.
/**
 * Definition for TreeNode.
 * type TreeNode struct {
 *     Val int
 *     Left *ListNode
 *     Right *ListNode
 * }
 */

type Stack []*TreeNode

func (s *Stack) Push(n *TreeNode) {
    *s = append(*s, n)
}

func (s *Stack) Pop() (n *TreeNode) {
    x := s.Len() - 1
    n = (*s)[x]
    *s = (*s)[:x]
    return
}

func (s *Stack) Len() int {
    return len(*s)
}



 func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
     if root == nil{ return nil }
     stack := new(Stack)
     m := make(map[*TreeNode]*TreeNode, 0)
     stack.Push(root)
     m[root] = nil
     for stack.Len() != 0{
         node := stack.Pop()
         if node.Left != nil{ 
             stack.Push(node.Left)
             m[node.Left] = node
         }
         if node.Right != nil{ 
             stack.Push(node.Right)
              m[node.Right] = node
         }
     }
     set := make(map[*TreeNode]bool, 0)
     for p!=nil{
         set[p] = true
         p = m[p]
     }
    
     for q!=nil{
         if set[q]{
             break
         }
         q = m[q]
         
     }
     
     return q
}

#3

Algorithm Below,

  1. In left and right sub trees, look for ‘p’ and ‘q’.
  2. If they match, return root.
  3. In the recursion, at each node check of left and right are not nil, and return the root.

Basically, we return nil for left and right, unless if the nodes match with ‘p’. So the only node with both left and right not nil is where we have the LCA.

 func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
     if (root==nil || root == p || root == q){ return root }
     left := lowestCommonAncestor(root.Left, p, q)
     right := lowestCommonAncestor(root.Right, p, q)
     if left!=nil && right!=nil{
         return root
     }
     if left!=nil{
         return left
     }
     return right
}

#4

Recursive code in Java.

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null || root==p || root==q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left!=null && right!=null){
            return root;
        }
        if(left!=null) return left;
        return right;
    }
}