Sunday, February 23, 2014

Lowest Common Ancestor in a Binary Tree

private static int LCABTUtil(Node root, int n1, int n2)
{
              //Base Condition
if(root == null) return 0;

int l = LCABTUtil(root.left, n1, n2);
int r = LCABTUtil(root.right, n1, n2);

// Node that has both n1 and n2 as descendants
if((l == 1 && r == 1))
{
System.out.println(root.data);
}
              // If node to be a descendant of  itself
              else if((l == 1 || r == 1) && (root.data == n1 || root.data == n2))
{
System.out.println(root.data);
}
              // Node that has one of descendant
               else
{
if(l == 1 || r == 1)
{
return 1;
}
}

if(root.data == n1 || root.data == n2)
{
return 1;
}
return 0;
}


static void lcaBT(Node root, int n1, int n2)
{
LCABTUtil(root, n1, n2);
}



References:
http://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/
http://leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-tree-part-i.html



No comments:

Post a Comment