Thursday, 28 April 2016

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 -

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


No comments:

Post a comment

t> UA-39527780-1 back to top