Write a function to connect all the adjacent nodes at the same level in a binary tree.
A Recursive Solution
An Iterative Solution
The outer loop, goes through all the levels and the inner loop goes through all the nodes at every level.
Also check http://massivealgorithms.blogspot.com/2014/06/leetcode-populating-next-right-pointers.html
Read full article from Connect nodes at same level using constant extra space | GeeksforGeeks
A Recursive Solution
if we traverse the nextRight node before the left and right children (root, nextRight, left,right), then we can make sure that all nodes at level i have the nextRight set, before the level i+1 nodes. 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).
1 -------------- Level 0
/ \
2 3 -------------- Level 1
/ \ / \
4 5 6 7 -------------- Level 2
/ \ / \
8 9 10 11 -------------- Level 3
void connect (struct node *p){ // Set the nextRight for root p->nextRight = NULL; // Set the next right for rest of the nodes (other than root) connectRecur(p);}/* Set next right of all descendents of p. This function makes sure thatnextRight of nodes ar level i is set before level i+1 nodes. */void connectRecur(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(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(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(p->right); } else connectRecur(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;}An Iterative Solution
The outer loop, goes through all the levels and the inner loop goes through all the nodes at every level.
/* 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); }}Read full article from Connect nodes at same level using constant extra space | GeeksforGeeks
