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;
}
void Solution::connect(TreeLinkNode* A)
{
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;
next_gen=advance(parent);
prev_child = NULL;
}
}