Lowest Common Ancestor in a Binary Tree

Lowest Common Ancestor in a Binary Tree

  August 06, 2017    

---

Explanation:

Here we will check when data is equal to either n1 or n2 return node , else recur for left & right , if left and right both points are not null it means that root have n1 , n2 for different subtree (LEFT /RIGHT).

check if one of the point is null then return the value which is not null.


Solution:

/* A Binary Tree node
class Node
{
    int data;
    Node left, right;
    Node(int item)
    {
        data = item;
        left = right = null;
    }
}*/
class hackerranksolutionc
{
Node LCA(Node root, int n1,int n2)
{
if(root==null)
return null;
if(root.data==n1 || root.data==n2)
return root;
Node left=LCA(root.left,n1,n2);
Node right= LCA(root.right,n1,n2);
if(left!=null && right!=null)
return root;
return (left!=null)?left:right;
}
}