## 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.

t> UA-39527780-1 