**Question:** Binary tree structure is defined as:

struct tree{

int val;

tree* left;

tree* right;

tree* rpeer;

};

At the beginning, all the rpeer nodes are assigned NULL. Write a program to populate correct value in rpeer for whole tree.

**Example:**

Input tree:Output tree: horizontal arrows are showing rpeer for every node.

**Answer:**As we are seeing that rpeer is next element at the same level. So if we are able to fetch the next element at same level, we are done. As per our prior knowledge, we can access these element using breadth first traversal.

Now only problem is how to check if we are at last element at any level. For this reason, we should be appending a delimiter (NULL in this case) to mark end of a level.

**Algorithm:**

Put root in queue.

Put NULL in queue.

While Queue is not empty

x = fetch first element from queue

If x is not NULL

x->rpeer <= top element of queue.

put left and right child of x in queue

else

if queue is not empty

put NULL in queue

end if

end while

return

**Code**:

#include <queue>

void right_peer(tree* root)

{

queue<tree*> que;

if (!root)

return;

tree *tmp, *l, *r;

que.push(root);

que.push(NULL);

while( !que.empty() )

{

tmp = que.front();

que.pop();

if(tmp != NULL)

{

tmp->rpeer = que.front();

l = tmp->left;

r = tmp->right;

if(l) que.push(l);

if(r) que.push(r);

}

else

{

if (!que.empty())

que.push(NULL);

}

}

return;

}

**Complexity:**Since we are just traversing each element in tree just once, complexity is O(n).

**Subscribe**- To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.
Anonymousvoid right_peer(Node* p) {

if (!p) return;

if (p->leftChild)

p->leftChild->rpeer= p->rightChild;

if (p->rightChild)

p->rightChild->rpeer= (p->rpeer) ?

p->rpeer->leftChild :

NULL;

connect(p->leftChild);

connect(p->rightChild);

}

Akash@Anonymous: What is connect()?

Amit Mittalconnect is basically the recursive call, it should be right_peer instead.