# Lang: C++, Complexity[Time, Space]: [O(n), O(1)]

#1

Lets say you have already created next pointers till level L. To create next pointer for level L+1, start with the first node on level L.

`````` level
L:    1  ->  2   ->  3  -> 4
/        \           /  \
/          \         /    \
L+1: 5            6       7      8
``````

Keep track of the previous node you encountered on the next level. For the current parent, explore the left and right child if they are not null in that order.

• If the prev_child is not set, that means we are looking at the leftmost node on the next level ( Lets store it as next_gen because we will begin the next iteration from this node ).
• Else you can assign prev_child->next as the first child of current parent you are on and update the prev_child node.
`````` level                            parent
v
L:           1  ->  2   ->  3  -> 4
/        \           /  \
/          \         /    \
L+1:        5    ->      6       7      8
^            ^
next_gen    prev_child
``````
`````` level
L:    1  ->  2   ->  3  -> 4
/        \           /  \
/          \         /    \
L+1: 5    ->      6   ->  7  ->  8
``````
``````TreeLinkNode* advance(TreeLinkNode* parent)
{   // Keep traversing siblings of parent until
// a sibling isn't a leaf then return its
// first child else return NULL

while(parent)
{
if(parent->left)
return parent->left;
else if(parent->right)
return parent->right;

parent=parent->next;
}
return NULL;
}
{
TreeLinkNode *parent = A, *prev_child=NULL, *next_gen=NULL;

if(parent==NULL)
return;

next_gen = ((A->left!=NULL)? A->left : A->right);
while(next_gen!=NULL)
{
while(parent!=NULL)
{
if(parent->left)
{
if(prev_child!=NULL)
prev_child->next = parent->left;
prev_child = parent->left;
}
if(parent->right)
{
if(prev_child!=NULL)
prev_child->next = parent->right;
prev_child = parent->right;
}
parent=parent->next;
}
parent = next_gen;