Lowest Common Ancestor in a Binary Tree.

Background

In one of the previous posts we saw how to find LCA of two nodes in a Binary search tree. In this post we will repeat the same question but now it's just a binary tree not a BST.

 Solution

    public static BTreeNode findLCA(BTreeNode root, int n1, int n2) {

        if (root == null) {
            return null;
        }

        if (root.getData() == n1 || root.getData() == n2) {
            return root;
        }

        BTreeNode leftNode = findLCA(root.getLeft(), n1, n2);
        BTreeNode rightNode = findLCA(root.getRight(), n1, n2);

        if (leftNode != null && rightNode != null) {
            return root;
        }

        return leftNode != null ? leftNode : rightNode;

    } 

I have posted complete solution with test cases on my GIT repo of interview question. You can find the code -

• LCA Finder Git

Logic is as follows -

• If one of the two nodes is the root, then the root itself is the common ancestor.
• If Node a and Node b lie in the left, their Lowest Common Ancestor is in the left.
• If Node a and Node b lie in the right,their Lowest Common Ancestor is in the right.
• Otherwise, root is the Lowest common ancestor.

Related Links

• Lowest Common Ancestor in a Binary Search Tree. (OSFG) 
• LCA Finder Git