Find LCA in Binary Tree, Find LCA in BST

By | January 30, 2016
Share the joy
  •  
  •  
  •  
  •  
  •  
  •  

I wrote finding lca long time ago. Today, I learned this more concise code for finding LCA in Binary Tree.

The idea is that if there is no p or q in bottom, return null. Or return p, q or root.

public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == p || root == q || root == null) {
        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;
}

Check my code on github: link

 

Below is the finding LCA in BST.

public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) {
        return null;
    }
    int max = Math.max(p.val, q.val);
    int min = Math.min(p.val, q.val);
    if (root.val >= min && root.val <= max) {
        return root;
    }
    return root.val > max ? lowestCommonAncestor(root.left, p, q) : lowestCommonAncestor(root.right, p, q);
}

Check my code on github: link