Populating next right pointers in each node (Sibling)

struct Node {
Node* leftChild;
Node* rightChild;
Node* nextRight;
}

Populate the nextRight pointers in each node.
You may assume that it is a full binary tree (ie, each node other than the leaves has two children.)

Naive Algorithm:-
1. Most likely this can be implemented recursively, because you can identify the linking of nodes as sub-problems.
2. The main difficulty of this problem is linking rightChild with the nextSibling of rightChild.
3. Each node has no parent pointer. Therefore, there is no way linking the rightChild with its nextSibling at a level.

as its naive you will find exactness of some more test cases covered in below working code .

Pseudo Code :-

void connect(Node* p)
{
if (!p) return;
if (p->leftChild)
p->leftChild->nextRight = p->rightChild;
if (p->rightChild)
p->rightChild->nextRight = (p->nextRight) ?
p->nextRight->leftChild :
NULL;
connect(p->leftChild);
connect(p->rightChild);
}



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

/* A binary tree node has data, pointer to left child
   and a pointer to right child */
struct node
{
    int data;
    struct node* left;
    struct node* right;
    struct node* nextRight;

};

/* 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);
}

void connect(struct node* p) {
  if (!p)
  return;
 
  if (p->left)
  {
    if(p->right)//its necessary else NULL Pointer Exception
          p->left->nextRight = p->right;

    else if(p->nextRight)
    {
        if(p->nextRight->left)/// we can add one more if(p->nextRight)
          p->left->nextRight=p->nextRight->left;
        else if(p->nextRight->right)
          p->left->nextRight=p->nextRight->right;
    }  
    else
         p->left->nextRight=NULL;//if all are null except that node at that level
  }

  if (p->right)
  {
    if(p->nextRight)
    {
        if(p->nextRight->left)//skipping checking the root null or not
            p->right->nextRight =p->nextRight->left;
        else if(p->nextRight->right)//skipping checking the root null or not
            p->right->nextRight =p->nextRight->right;
    }
    else
             p->right->nextRight=NULL;
  }
  connect(p->left);
  connect(p->right);
}

/* Driver program to test above functions*/
int main()
{
  struct node *root = newNode(1);
  root->left        = newNode(2);
  root->right       = newNode(3);
  root->left->left  = newNode(4);
  root->left->right  = newNode(5);
  root->right->left= newNode(6);
  root->right->right= newNode(7);
  root->left->left->left  = newNode(8);
  root->left->left->right  = newNode(9);
  root->left->right->left  = newNode(10);
  root->left->right->right  = newNode(11);
  root->right->left->left= newNode(12);
  root->right->left->right= newNode(13);
  root->right->right->left= newNode(14);
  root->right->right->right= newNode(15);



  connect(root);
 
  printf( " %d %d %d ", root->left->left->nextRight->data,root->left->right->nextRight->data,root->right->left->nextRight->data);
  printf(" %d %d %d ",root->left->left->left->nextRight->data,root->left->left->right->nextRight->data,root->right->right->left->nextRight->data);//,root->right->right->right->nextRight->data); it will be null


  getchar();
  return 0;
}

Time Complexity O(N^2)
Space Complexity O(1)
Run Here https://ideone.com/lTPuY


2nd Method Using Queue
Just modified the structure of node of tree
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.

Efficient 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:

Algo is Correct Code Modification Needed :P  BDW Enjoy its Great Spoon Feeding :)

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


/* A binary tree node has data, pointer to left child
and a pointer to right child */
typedef struct node
{
int data;
struct node* left;
struct node* right;
struct node* nextRight;

}node;

typedef node * Tree;

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

return(node);
}


void connect(Tree root)
{
std::list que; //Queue to store tree nodes
que.push_back(root);
que.push_back(NULL); //null is the delimeter to show end of the level

if (!root)
return;

Tree *l, *r;

while(!que.empty())
{
Tree *tmp= que.front();
que.pop_front();

if(tmp != NULL)
{
tmp->nextRight= que.front();
l = tmp->left;
r = tmp->right;
if(l) que.push_back(l);
if(r) que.push_back(r);
}
else
{
if (!que.empty())
que.push_back(NULL);
}
}
return;
}

int main()
{
Tree root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left= newNode(6);
root->right->right= newNode(7);
root->left->left->left = newNode(8);
root->left->left->right = newNode(9);
root->left->right->left = newNode(10);
root->left->right->right = newNode(11);
root->right->left->left= newNode(12);
root->right->left->right= newNode(13);
root->right->right->left= newNode(14);
root->right->right->right= newNode(15);



connect(root);

printf( " %d %d %d ", root->left->left->nextRight->data,root->left->right->nextRight->data,root->right->left->nextRight->data);
printf(" %d %d %d ",root->left->left->left->nextRight->data,root->left->left->right->nextRight->data,root->right->right->left->nextRight->data);//,root->right->right->right->nextRight->data); it will be null


getchar();
return 0;
}

Time Complexity O(N^2)
Run Here  https://ideone.com/8Kgnb
Space Complexity O(1)
R