CareerCup

Here is my understanding of the question:
Given 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

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

First find the root node using the parent pointer. Then do BFS level by level. After the BFS encounters the node we are interested in, start printing the rest of nodes in the same level. Stop traversing after the current level is done.

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.

Not understanding the question, can you please provide an example?

Run BFS and Store the value with its level in a hashmap.

Read the value which is right next to the given value.

1. if root->left = node then root->right is answer
2. if root->right = node then root->root->left is answer

if both condition is false then node is not having any right sibling

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");
     }
}

1. if node->root->left = node then node->root->right is answer
2. if node->root->right = node then

if(node->root->root->right->left != node->root->left )
then node->root->root->right->left is answer

if above condition are false (NULL) then node is not having any right sibling