Lowest Common Ancestor

236 LCA - given 2 nodes and root in Binary tree

• Time O(n), space O(h)

  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode node1, TreeNode node2) {
   // 碰到node1 or node2 就返回
    if(root == null || root == node1 || root == node2){
        return root;
    }
  
    TreeNode left = lowestCommonAncestor(root.left, node1, node2); 
    TreeNode right = lowestCommonAncestor(root.right, node1, node2);
  
    if( left != null && right != null){
        return root;
    }
    if(left != null){
        return left;
    }
    if(right != null){
        return right;
    }
    return null;
  }

LCA - given 2 nodes with parent pointer in same binary tree

• Get depths of each nodes, make deeper node to the same level of another

• Time O(h), Space O(1)

public static BinaryTree<Integer> LCA(TreeNode node0, TreeNode node1) {
  int depth_0 = depthGetter(node0), depth_1 = depthGetter(node1);

  // adjust node0 to make it deeper than node1
  if(depth_1 > depth_0){
    BinaryTree<Integer> tmp = node0;
    node0 = node1;
    node1 = tmp;
  }

  int diff = Math.abs(depth_0 - depth_1);

  while( diff-- > 0){
    node0 = node0.parent;
  }

  while(node0 != node1){
    node0 = node0.parent;
    node1 = node1.parent;
  }

  return node0;
}

LCA - given 2 nodes with parent pointer, optimize for close ancestor

• Use Hashtable

• Time and Space O(D0 + D1)

public static BinaryTree<Integer> LCA(TreeNode node0, TreeNode node1) {
  Set<BinaryTree<Integer>> s = new HashSet<>();
  while(node0 != null || node1 != null){
    if(node0 != null){
      if (!s.add(node0)){
        return node0;
      }
      node0 = node0.parent;
    }
    if(node1 != null){
      if (!s.add(node1)){
        return node1;
      }
      node1 = node1.parent;
    }
  }
  return null;
}

235 LCA with BST

• Worst case O(h)

• Keep search the root in range [node0, node1]

  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if(p.val > q.val){
        TreeNode tmp = p;
        p = q;
        q = tmp;
    }
    while(root.val < p.val || root.val > q.val){
        while(root.val < p.val) root = root.right;
        while(root.val > q.val) root = root.left;
    }
    return root;
  }

1123. Lowest Common Ancestor of Deepest Leaves

Given a rooted binary tree, return the lowest common ancestor of its deepest leaves.

class Solution:
    def lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:
        def helper(node):
            if not node:
                return 0, None
            d1, t1 = helper(node.left)
            d2, t2 = helper(node.right)
            
            if d1 > d2: return d1+1, t1
            elif d1 < d2: return d2+1, t2
            else: return d1+1, node
            
        return helper(root)[1]