NetApp Interview Question
Country: India
Interview Type: In-Person
1. if node->root->left = node then node->root->right is answer
2. if node->root->right = node then node->root->root->right->left is answer
if both condition are false (NULL) then node is not having any right sibling
You can have something like this:
O
/ \
O O
/ \ / \
X P1 P2 P3
X is the current node. We are interested to find the right node for X.
P1 , P2 , P3 and null are the possibilities.
so I think you should keep in mind the level on which you are interested to find the "right" node. Use another variable to keep track of the current level. Go test each of the three possibilities and if non of them is !null then return null which means that you have no "right" node.
Run BFS and Store the value with its level in a hashmap.
Read the value which is right next to the given value.
this is the code i wrote based on Laxmi's assumption.
public Node func(Node n)
{
Node p= n;
if(p.getParent().getRight() != null)
{
p = p.getParent().getRight();
return p;
}
else
{
while(p.getParent().getRight() == null || p.getParent() == null)
{
p = p.getParent();
x++;
}
if(p.getParent() != null)
{
Node y = p.getParent().getRight();
while( x!=0)
{
if(y.getLeft() != null)
{
y = y.getLeft();
x--;
}
else
{
y = y.getRight();
x--;
}
}
return y;
}
}
else
{
print("no sibling");
}
}
Here is my understanding of the question:
- Laxmi Narsimha Rao Oruganti December 12, 2012Given a binary tree - where each node has three pointers namely parent, left Child, right Child. Find the 'right' (as in right direction) sibling of any given node.
Answer:
0.1) Assumption: Assume that the actual node pointer is given
1) Integer variable: 'hop count' initialized to zero
2) Walk-up the tree using parent pointer (keep track of the actual node - say prev)
2.1) Increment hop count
2.2) If 'prev' is node's left child and node's right is not null, stop walk-up and quit the loop
2.3) continue the walk-up
3) Initialize tempHops = hopCount - 1, subTree = node's right
4) Do depth-first traversal on sub-Tree (i.e. prefer left child over right child if exists)
4.1) For every walk down, decrement tempHops
4.2) For every walk (back up), increment tempHops
4.2) When tempHops is 'zero', that node is right sibling
5) If we exhausted the subtree and did not hit tempHops zero
5.1) It means the right sub-tree is not of same height at this node level
5.2) Repeat step (2)-(4) with continuation of hopCount (without resetting it to zero)
5.3) If we reached the root node and never could find tempHops zero, it means that there is no right sibling at the level of a given node
Thanks,
Laxmi