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