Linear time, constant space, no Queue with easy Implementation


#1

Comment body goes here.
Think like this way, you are at i’th level and next pointer for all node for i’th level are fixed somehow and you are at the front node of the i’th level, how do you fix the next pointers for all node of next level?
Boomm: You need the front pointer for the next level so that you start same journey again and a pointer that helping to fixe next pointers for the next level’s nodes that will have to start from the front node of the next level.

void Solution::connect(TreeLinkNode* A) {

 auto root = A;
 
 while(root)
 {
     TreeLinkNode* n_root = NULL;
     TreeLinkNode* curr = NULL; 
     
     while(root)
     {
         if(root->left)
         {
             if(!n_root) n_root = root->left, curr = root->left;
             else curr->next = root->left, curr = curr->next;
             
         }
         if(root->right)
         {
             if(!n_root) n_root = root->right, curr = root->right;
             else curr->next = root->right, curr = curr->next;
         }
         
         root = root->next; 
     }
     
     root = n_root; 
 }
 
 //return A; 

}


#2

Hey, I had given up on this question to do it another day and then i read just the first line of your hint. God I have never been so crystal clear of the solution that came up on my mind in a second. It was an awesome hint. Thanks!! :smile: