Yahoo Interview Question
Software Engineer / DevelopersCountry: United States
O(n) solution:
public TreeNode rightMostCousin(TreeNode root, int targetKey)
{
LinkedList<TreeNode> q = new LinkedList<TreeNode>();
int count = 0;
q.add(root);
count++;
boolean targetLevel = false;
while(!q.isEmpty())
{
TreeNode node = q.remove();
count--;
if((node.left!=null && node.left.key == targetKey) || (node.right!=null && node.right.key == targetKey))
targetLevel = true;
if(node.left != null) q.add(node.left);
if(node.right != null) q.add(node.right);
if(count == 0)
{
count = q.size();
if(targetLevel)
{
TreeNode cousin = null;
while(!q.isEmpty())
{
cousin = q.remove();
}
return cousin;
}
}
}
return null;
}
The way I solved it was first to find the grandfather node of a tree(if one exists) using recursion. Then I checked if the target node was a part of the subtree rooted at the left child of grandfather. If so, there is a rightmost cousin. And we find the same in the subtree rooted at the right child of grandfather. Here is the code in C++.
General::TreeNode<int>* getGrandFather(General::TreeNode<int>* root, int target,
General::TreeNode<int>* father,General::TreeNode<int>* grand_father)
{
if(!root)
return NULL;
if(root->value()==target)
return grand_father;
General::TreeNode<int>* left_res;
General::TreeNode<int>* right_res;
left_res = getGrandFather(root->getLeftChild(),target,root,father);
right_res = getGrandFather(root->getRightChild(),target,root,father);
if(!left_res)
return right_res;
else if(!right_res)
return left_res;
else return NULL;
}
General::TreeNode<int>* getCousin(General::TreeNode<int>* root,int target)
{
General::TreeNode<int>* grandpa = getGrandFather(root,target,NULL,NULL);
std::cout << grandpa->value();
int grandson1,grandson2,grandson3,grandson4;
if(grandpa)
{
grandson1 = grandpa->getLeftChild()->getLeftChild()->value();
grandson2 = grandpa->getLeftChild()->getRightChild()->value();
if(grandson1==target || grandson2==target)
{
if(grandpa->getRightChild())
if(grandpa->getRightChild()->getRightChild())
return grandpa->getRightChild()->getRightChild();
else
return grandpa->getRightChild()->getLeftChild();
else
return NULL;
}
}
return NULL;
}
findit(Node x, Node target)
{
if(x==nil) return -1; //target not down this path
if(x==target) return 0; //target found, return 0 as dist. above it
// else check for target down all paths (children)
distanceabove = -1;
for(temp=x.children; temp!=nil ; temp=temp.nextchild)
{
distabove=findit(temp, target);
if( distabove >= 2 ) return 2; //helps prune tree (optimization .. I hope!)
if( distabove != -1 ) break; //target was along this path
}
if(distabove == -1) return -1; //target is nowhere in our subtree
distabove++; //add 1 to distance (for extra hop up to us)
if(distabove == 2) { //we are 2 hops above target, thus grandma
for(temp=x.children; temp && temp.next; ) //find rightmost aunt of target
temp=temp.nextchild;
for(temp=temp.children, prev=nil; temp && temp.next; ) //aunt's 2 r.m. daughters
prev=temp, temp=temp.nextchild;
if(temp && temp != target)
cout << temp << " is rightmost cousin\n"; //rightmost daughter if not me
elif(temp && prev )
cout << prev<< " is rightmost cousin\n"; //else try second rightmost
}
return distabove;
}
Typed it raw, expect the unexpected.
int printRightMostNeighbor(struct bs *b) //i.e., neighbor in level-order sense without using level-order or bfs
{
int level1=0;
int level2=0;
if(b==NULL || b->parent==NULL)
return NULL;
if(b->parent->rc!=NULL && b->parent->rc!=b)
return b->parent->rc;
struct bst *tmp=NULL;
struct bst *tmp1=b;
while(b->parent!=NULL)
{
tmp=b;
b=b->parent;
level1++;
if(b->rc!=NULL && b->rc!=tmp)
break;
}
while(level2!=level1-1)
{
if(b->rc==NULL)
return NULL;
b=b->rc;
level2++;
}
if(b->rc==tmp1)
return NULL;
if(b->lc!=NULL)
return b->lc;
else if(b->rc!=NULL)
return b->rc;
else
return NULL;
}
Node structure will contain "level" field and "parent" field. Perform BFS on the tree. Keep track of the node that was inserted just before the current node. Once the target node is found look for level change. If the parent of the target node and the "before" node is the same after level changes, then the target node has no cousin. Else, the "before" node is the rightmost cousin.
I'm going to make three time-saving assumptions:
i. Children have a parent pointer
ii. Each node can have at most 2 children
iii. a cousin will be defined here as any node in the tree which has the same distance from the root as the input node.
All three of these can be easily remedied by adding onto the following design, but I'm lazy today.
TreeNode find_cousin(TreeNode a){
int h = 0;
TreeNode tmp = a;
while(tmp.parent != null){
tmp = tmp.parent;
h++;
}
TreeNode x = find_rec(tmp, h, a);
return x;
}
TreeNode find_rec(TreeNode a, int h, TreeNode avoid){
if(a == null || a == avoid.parent) return null;
if(h==0)return a;
TreeNode x = find_rec(a.right, h - 1, avoid);
if(x == null) x = find_rec(a.left, h - 1, avoid);
return x;
}
Why does it work? It will seek out the rightmost cousin of the given node, even if that cousin is to the left of the given node. It will avoid the input node (given as avoid) and its sibling by rejecting at the parent level. If going right doesn't work, either because it hits the avoid's parent or because it reaches a leaf node before h = 0, it will attempt to go left. If necessary, it will traverse all nodes in the tree from the input's height and upwards, but will stop the moment it finds a node that is at the same height as the input, which we can assume is the rightmost since it will always look right as far as it can from any one parent node before moving on to try the left.
// given question : Given Binary Tree, and a node, find the right most cousin, . In other words, given a node, find the right-most node in the same level;
TreeNode* rightMostCousin(TreeNode* root, TreeNode* gNode)
{
queue<TreeNode*> q;
int nCurrent(0), nNext(0);
TreeNode* ret(NULL);
if (root != NULL) { q.push(root); nCurrent++; }
while (!q.empty())
{
TreeNode* cNode = q.front(); q.pop();
nCurrent--;
if (nNext == 0) { ret = cNode; }
// if given node, then return ans, which is the rightmost-node in the given binary tree
if (cNode == gNode) return ret;
if (cNode->left != NULL) { q.push(cNode->right); nNext++; }
if (cNode->right != NULL) { q.push(cNode->left); nNext++; }
// go to the next level
if (nCurrent == 0) {
nCurrent = nNext;
nNext = 0;
}
}
return NULL;;
}
(1)As the tree's structure is unknown, we might have to use a general method.
(2)Because the rightest cousin is at the same level with the given node, we can traverse the tree by level to find the level of the given node. Meanwhile the fact is when we find the given node in a level loop, the last node of the loop will just be our target!
Following is my C++ code:
Node* getRightestCousin(Node* root, Node* p)
{
if(root == NULL || p == NULL || root == p) return NULL;
queue<Node*> q;
Node* tmp;
int levelCount, i;
q.push(root);
while(!q.empty()){
for(i = 0, levelCount = q.size(); i < levelCount; ++i){
tmp = q.front();
q.pop();
if(tmp != p){ //may not in this level, so push in next level's nodes
if(tmp->left) q.push(tmp->left);
if(tmp->right) q.push(tmp->right);
}
else{ //only need to find the last node in this level
Node* t = NULL; //this is because p may be the rightest node in its level
for(++i; i < levelCount; ++i){
t = q.front();
q.pop();
}
return t;
}
}
}
return NULL; //can not find p in this tree
}
O(n) solution:
- zahidbuet106 May 26, 2014