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;
}
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;
    }
}