YulongW
8/28/2017 - 1:50 AM

Lowest Common Ancestor of a Binary Tree

Lowest Common Ancestor of a Binary Tree

// This code assumes both nodes exist

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;
  }
  return left != null ? left : right;
}