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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
    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