Wednesday, June 11, 2014

Find deepest common ancestor in BST


Conditions for finding ca in bst:
        9
      /
    5
   /  \
3     8

3,8 ca is 5
5,3 ca is 9


static Node findDeepeastCommonAncestor(Node root, int d1, int d2){
if(root == null) return null;

if(!search(root, d1) || !search(root, d2)) return null;

if(d1 > d2)
{
int tmp = d1;
d1 = d2;
d2 = tmp;
}

return findDeepeastCommonAncestorUtil(root, d1, d2);
}

private static Node findDeepeastCommonAncestorUtil(Node root, int d1, int d2){
if(root == null) return null;

if(root.val > d1 && root.val < d2) return root;

if(root.val > d1 && root.val > d2)
{
if(root.left != null && root.left.val == d1) return root;

return findDeepeastCommonAncestorUtil(root.left, d1, d2);
}

if(root.val < d1 && root.val < d2)
{
if(root.right != null && root.right.val == d1) return root;

return findDeepeastCommonAncestorUtil(root.right, d1, d2);
}

return null;
}


private static boolean search(Node root, int data) {

if(root == null) return false;

if(root.val == data) return true;

if(root.val > data) return search(root.left, data);
return search(root.right, data);
}

No comments:

Post a Comment