Interview Questions

Lowest Common Ancestor of a Binary Tree

					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==p && right==q) || (left==q && right==p)) return root;
        if (left!=null) return left;
        return right;

Since for every node in a binary tree it is guaranteed that we have a single unique path, we can check “post order” if we found both nodes that we search in the right and left sub trees. in any case we found such node, it is the LCA.

Leave a Reply

Your email address will not be published. Required fields are marked *