Question: Binary tree structure is defined as:

`struct tree{  int val;  tree* left;  tree* right;  tree* rpeer;    };`

‘rpeer’ will have the address of next node of same level. For last node at any level, rpeer will be NULL.

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 emptyx = fetch first element from queueIf x is not NULL  x->rpeer  <=  top element of queue.  put left and right child of x in queueelse  if queue is not empty  put NULL in queueend ifend whilereturn`

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).