## CapitalIQ Interview Question

Software Engineer / Developerstree *least(tree *node,int val1,int val2)

{

tree *current=node;

while(1)

{

if(current->data<val1&¤t->data<val2)

{

if(current->right->data==val1||current->right->data==val2)

return current;

else

current=current->right;

}

else if(current->data>val1&¤t->data>val2)

{

if(current->left->data==val1||current->left->data==val2)

return current;

else

current=current->left;

}

else

return current;

}

}

Btree* least(Btree *b ,int k1,int k2)

{

if(contains(b->lc,k1)&&contains(b->rc,k2) || contains(b->lc,k2)&&contains(b->rc,k1))

{

return b;

}

else if(contains(b->lc,k1)&&contains(b->lc,k2))

return least(b->lc,k1,k2);

else

return least(b->rc,k1,k2);

}

bool contains(Btree *bt,int k)

/* level order traversal to find whether node containing value k is present or not */

{

arrayQueue <Btree *> q; //queue of binary tree nodes

while(bt!=NULL)

{

if(bt->d==k)

return true;

//put bt's child on queue

if(bt->lc!=NULL)

q.push(bt->lc);

if(bt->rc!=NULL)

q.push(bt->rc);

//get next node to visit

try{

bt=q.front();

}

catch(queueEmpty){

return false;

}

q.pop();

}

}

If p!=q, reduce to LCA problem

- Anonymous September 27, 2009If p==q, DFS to find the parent of p