Connect Nodes at same level /Populate next right

Write a function to connect all the adjacent nodes at the same level in a binary tree.
OR
Populate nextRight pointer with next sibling of each node in a binary tree

 Structure of the given Binary Tree node is like following.

struct node{   int data;   struct node* left;   struct node* right;   struct node* nextRight; }

Initially, all the nextRight pointers point to garbage values. Your function should set these pointers to point next right for each node.
Example

Input Tree
       A
      / \
     B   C
    / \   \
   D   E   F

Output Tree
       A--->NULL
      / \
     B-->C-->NULL
    / \   \
   D-->E-->F-->NULL

Solution for Complete BTs

Method 1:Naive Recursion[Only for Complete Binary Tree]

1.The first key to solving this problem is we have the nextRight pointer. Assume that the nextRight pointers are already populated for this level. How can we populate the next level? Easy… just populate by iterating all nodes on this level.
2.Another key to this problem is you have to populate the next level before you go down to the next level, because once you go down, you have no parent pointer, and you would have hard time populating

Method 2 :Modified Pre order Traversal[Works only for complete BT]

In this method we set nextRight in Pre Order fashion to make sure that the nextRight of parent is set before its children. When we are at node p, we set the nextRight of its left and right children. Since the tree is complete tree, nextRight of p’s left child (p->left->nextRight) will always be p’s right child, and nextRight of p’s right child (p->right->nextRight) will always be left child of p’s nextRight (if p is not the rightmost node at its level). If p is the rightmost node, then nextRight of p’s right child will be NULL.

Note:The above two methods only works for complete BTs.WHY

Consider the tree given below

____________1
          /    \
        2        3
       / \      /  \
      4   5    6    7
     / \           / \
    8   9        10   11

In Method 2, we set the nextRight pointer in pre order fashion.  When we are at node 4, we set the 

nextRight of its children which are 8 and 9(the nextRight of 4 is already set as node 5). nextRight of 8 

will simply be set as 9, but nextRight of 9 will be set as NULL which is incorrect.  We can’t set the 

correct nextRight, because when we set nextRight of 9, we only have nextRight of node 4 and ancestors 

of node 4, we don’t have nextRight of nodes in right subtree of root.

Solution for BTs which are not complete

Method 3:Modified Pre Order with nextRight

In the method 2 we traversed the nodes in pre order fashion. 

Instead of traversing in Pre Order fashion (root, left, 
right), if we traverse the nextRight node before the left and right 
children (root, nextRight, left), then we can make sure that all nodes 
at level i have the nextRight set, before the level i+1 nodes.  Let us 
consider the following example.In the above example,

The method 2 fails for right child of node 4.In this method, we make
sure that all nodes at the 4′s level (level 2) have nextRight set, 
before we try to set the nextRight of 9.  So when we set the nextRight 
of 9, we search for a nonleaf node on right side of node 4 
(getNextRight() does this for us). 

Code:

#include <stdio.h>
#include <stdlib.h>

struct node
{
  int data;
  struct node *left;
  struct node *right;
  struct node *nextRight;
};

typedef struct node* Node;

//Method 2

void connectRecur(struct node* p);

void connect_pre (struct node *p)
{
    p->nextRight = NULL;

    connectRecur(p);
}

void connectRecur(struct node* p)
{
  if (!p)
    return;

  // Set the nextRight pointer for p's left child
  if (p->left)
    p->left->nextRight = p->right;

  // Set the nextRight pointer for p's right child
  // p->nextRight will be NULL if p is the right most child at its level
  if (p->right)
    p->right->nextRight = (p->nextRight)? p->nextRight->left: NULL;

  // Set nextRight for other nodes in pre order fashion
  connectRecur(p->left);
  connectRecur(p->right);
}

//Method 1


void connect_Naive(Node p) {
  if (p == NULL)
    return;
  if (p->left == NULL || p->right == NULL)
    return;
  Node rightSibling;
  Node p1 = p;
  while (p1) {
    if (p1->nextRight)
      rightSibling = p1->nextRight->left;
    else
      rightSibling = NULL;
    p1->left->nextRight = p1->right;
    p1->right->nextRight = rightSibling;
    p1 = p1->nextRight;
  }
  connect_Naive(p->left);
}

//Method 3

void connectRecur_BT(struct node* p);
struct node *getNextRight(struct node *p);

void connect_BT (struct node *p)
{
    p->nextRight = NULL;

    connectRecur_BT(p);
}

/* Set next right of all descendents of p. This function makes sure that
nextRight of nodes ar level i is set before level i+1 nodes. */
void connectRecur_BT(struct node* p)
{
    // Base case
    if (!p)
       return;

    /* Before setting nextRight of left and right children, set nextRight
    of children of other nodes at same level (because we can access
    children of other nodes using p's nextRight only) */
    if (p->nextRight != NULL)
       connectRecur_BT(p->nextRight);

    /* Set the nextRight pointer for p's left child */
    if (p->left)
    {
       if (p->right)
       {
           p->left->nextRight = p->right;
           p->right->nextRight = getNextRight(p);
       }
       else
           p->left->nextRight = getNextRight(p);

       /* Recursively call for next level nodes.  Note that we call only
       for left child. The call for left child will call for right child */
       connectRecur_BT(p->left);
    }

    /* If left child is NULL then first node of next level will either be
      p->right or getNextRight(p) */
    else if (p->right)
    {
        p->right->nextRight = getNextRight(p);
        connectRecur_BT(p->right);
    }
    else
       connectRecur_BT(getNextRight(p));
}

/* This function returns the leftmost child of nodes at the same level as p.
   This function is used to getNExt right of p's right child
   If right child of p is NULL then this can also be used for the left child */
struct node *getNextRight(struct node *p)
{
    struct node *temp = p->nextRight;

    /* Traverse nodes at p's level and find and return
       the first node's first child */
    while(temp != NULL)
    {
        if(temp->left != NULL)
            return temp->left;
        if(temp->right != NULL)
            return temp->right;
        temp = temp->nextRight;
    }

    // If all the nodes at p's level are leaf nodes then return NULL
    return NULL;
}

struct node* newnode(int data)
{
  struct node* node = (struct node*)
                       malloc(sizeof(struct node));
  node->data = data;
  node->left = NULL;
  node->right = NULL;
  node->nextRight = NULL;

  return(node);
}

int main()
{

  /* Constructed binary tree is
            10
          /   \
        8      2
      /
    3
  */
  struct node *root = newnode(10);
  root->left        = newnode(8);
  root->right       = newnode(2);
  root->left->left  = newnode(3);
  

  struct node *root1 = newnode(10);
  root1->left        = newnode(8);
  root1->right       = newnode(2);
  root1->left->left  = newnode(3);
  root1->right->right       = newnode(90);


  connect_pre(root);
//connect_Naive(root);
  connect_BT(root1);

  // Let us check the values of nextRight pointers
  printf("Following are populated nextRight pointers in the tree "
          "(-1 is printed if there is no nextRight) \n");
  printf("nextRight of %d is %d \n", root->data,
         root->nextRight? root->nextRight->data: -1);
  printf("nextRight of %d is %d \n", root->left->data,
        root->left->nextRight? root->left->nextRight->data: -1);
  printf("nextRight of %d is %d \n", root->right->data,
        root->right->nextRight? root->right->nextRight->data: -1);
  printf("nextRight of %d is %d \n", root->left->left->data,
        root->left->left->nextRight? root->left->left->nextRight->data: -1);

  //Incomplete BT

  printf("\n");
  
  /*
  Constructed binary tree is
              10
            /   \
          8      2
        /         \
      3            90
  
  */

  printf("Following are populated nextRight pointers in the tree "
          "(-1 is printed if there is no nextRight) \n");
  printf("nextRight of %d is %d \n", root1->data,
         root1->nextRight? root1->nextRight->data: -1);
  printf("nextRight of %d is %d \n", root1->left->data,
        root1->left->nextRight? root1->left->nextRight->data: -1);
  printf("nextRight of %d is %d \n", root1->right->data,
        root1->right->nextRight? root1->right->nextRight->data: -1);
  printf("nextRight of %d is %d \n", root1->left->left->data,
        root1->left->left->nextRight? root1->left->left->nextRight->data: -1);

  getchar();
  return 0;
}

Method 4:Iterative Approach

In the iterative version, we use nested loop. The outer loop, goes 
through all the levels and the inner loop goes through all the nodes at 
every level.  This solution uses constant space.

Code:

#include <stdio.h>
#include <stdlib.h>

struct node
{
    int data;
    struct node *left;
    struct node *right;
    struct node *nextRight;
};

/* This function returns the leftmost child of nodes at the same level as p.
   This function is used to getNExt right of p's right child
   If right child of is NULL then this can also be sued for the left child */
struct node *getNextRight(struct node *p)
{
    struct node *temp = p->nextRight;

    /* Traverse nodes at p's level and find and return
       the first node's first child */
    while (temp != NULL)
    {
        if (temp->left != NULL)
            return temp->left;
        if (temp->right != NULL)
            return temp->right;
        temp = temp->nextRight;
    }

    // If all the nodes at p's level are leaf nodes then return NULL
    return NULL;
}

/* Sets nextRight of all nodes of a tree with root as p */
void connect(struct node* p)
{
    struct node *temp;

    if (!p)
      return;

    // Set nextRight for root
    p->nextRight = NULL;

    // set nextRight of all levels one by one
    while (p != NULL)
    {
        struct node *q = p;

        /* Connect all childrem nodes of p and children nodes of all other nodes
          at same level as p */
        while (q != NULL)
        {
            // Set the nextRight pointer for p's left child
            if (q->left)
            {
                // If q has right child, then right child is nextRight of
                // p and we also need to set nextRight of right child
                if (q->right)
                    q->left->nextRight = q->right;
                else
                    q->left->nextRight = getNextRight(q);
            }

            if (q->right)
                q->right->nextRight = getNextRight(q);

            // Set nextRight for other nodes in pre order fashion
            q = q->nextRight;
        }

        // start from the first node of next level
        if (p->left)
           p = p->left;
        else if (p->right)
           p = p->right;
        else
           p = getNextRight(p);
    }
}

/* UTILITY FUNCTIONS */
/* Helper function that allocates a new node with the
   given data and NULL left and right pointers. */
struct node* newnode(int data)
{
    struct node* node = (struct node*)
                        malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    node->nextRight = NULL;

    return(node);
}

/* Driver program to test above functions*/
int main()
{

    /* Constructed binary tree is
              10
            /   \
          8      2
        /         \
      3            90
    */
    struct node *root = newnode(10);
    root->left        = newnode(8);
    root->right       = newnode(2);
    root->left->left  = newnode(3);
    root->right->right       = newnode(90);

    // Populates nextRight pointer in all nodes
    connect(root);

    // Let us check the values of nextRight pointers
    printf("Following are populated nextRight pointers in the tree "
           "(-1 is printed if there is no nextRight) \n");
    printf("nextRight of %d is %d \n", root->data,
           root->nextRight? root->nextRight->data: -1);
    printf("nextRight of %d is %d \n", root->left->data,
           root->left->nextRight? root->left->nextRight->data: -1);
    printf("nextRight of %d is %d \n", root->right->data,
           root->right->nextRight? root->right->nextRight->data: -1);
    printf("nextRight of %d is %d \n", root->left->left->data,
           root->left->left->nextRight? root->left->left->nextRight->data: -1);
    printf("nextRight of %d is %d \n", root->right->right->data,
           root->right->right->nextRight? root->right->right->nextRight->data: -1);

    getchar();
    return 0;
}