CareerCup

I agree with Musheka. Because it's a binary tree, the solution is sketched out like this:

void traverse(node* &pnode){
if (pnode == NULL) return;
//get the left child
node *left = pnode->leftChild;
//get the right child
node *right = pnode->rightChild;

//populate the nextRight
left->nextRight = right;
right->nextRight = null;
traverse(left);
traverse(right);
}

call traverse(root);

I am sorry I did not understand the question. What is nextRight supposed to point to?

I think so it is the right node to the current node in the same level

does the nextRight mean the next inorder succesor when the rightChild is deleted ?

I agree with Musheka. Because it's a binary tree, the solution is sketched out like this:

void traverse(node* &pnode){
if (pnode == NULL) return;
//get the left child
node *left = pnode->leftChild;
//get the right child
node *right = pnode->rightChild;

//populate the nextRight
left->nextRight = right;
right->nextRight = null;
traverse(left);
traverse(right);
}

call traverse(root);

@Anonymous..Not every right child has a null "next right"..only the right extreme node in the same level points to null.others point to a particular node.

@Anonymous..Not every right child has a null "next right"..only the right extreme node in the same level points to null.others point to a particular node.

Another interpretation is, nextRight means the next sibling node to the right.

In this case, do a BFS and chain together nodes of the same level.

But how will you do BFS in a tree when we don't have right pointers???

node linkRightNode(node*
root)
{
if(root==null)
return null;
if(root->left==null || root->right==null)
return root;
while(root!=null)
{
root->left->nextRight = root->right;
linkRightNode(root->left);
linkRightNode(root->right);
}
}

why BFS? It's a binary tree with only 2 children. At any node you know the configuration of left and right pointer sitting from a parent node and decide what goes where and set accordingly.

Correct Code:

node linkRightNode(node*
root)
{
if(root==null)
return null;
if(root->left==null || root->right==null)
return root;
node* left = linkRightNode(root->left);
node* right = linkRightNode(root->right);
if(left!=null && right!=null)
left->nextRight = right;
}
}

If nextRight points to the next node to the current node in the same level:

1 void populate(Node * root)
2 {
3 if(!root)
4 return;
5 Node * left = root->left;
6 Node * right = root->right;
7 if(left)
8 left->nextRight = right;
9 if(right)
10 right->nextRight = (root->nextRight) ? NULL : root->nextRight->left;
11 populate(left);
12 populate(right);
13 }

Basic idea:
In order to link all nodes in the same level, we have to traversal nodes by level. For each level, we traverse from the most right node to the most left node using a queue and build a list for each level.

37 void connect_nodes_by_level(Node * root)
 38 {
 39     if(!root)
 40         return;
 41     queue<Node*> q;
 42     q.push(root);
 43     int nump = 1;
 44     int numc = 0;
 45     Node * p = NULL;
 46     while(nump)
 47     {
 48         Node * n = q.front();
 49         q.pop();
 50         n->nextRight = p;
 51         p = n;
 52         nump--;
 53         if(n->right)
 54         {
 55             q.push(n->right);
 56             numc++;
 57         }
 58         if(n->left)
 59         {
 60             q.push(n->left);
 61             numc++;
 62         }
 63         if(!nump)
 64         {
 65             nump = numc;
 66             numc = 0;
 67             p = NULL;
 68         }
 69     }

Keep a static pointer tmp in breadth first traversal and set tmp to root at starting. than set temp->nextright to node popped from queue. and set tmp to newly popped node. At the end you will get a tree with all levels connected left to right and right most node connected to left node of next level. so now set null in all right most nodes.

A simple recursive post order traversal and checking for left and right nodes is sufficient to do this.

def nextright(root):
  if not root:
    return
  nextright(root.left)
  nextright(root.right)
  if root.left and root.right:
    root.left.nextRight = root.right