Simple C++ solution. Everyone Must Know #INCLUDE(COMMENTS)

#1

What we are doing here is the following.
Taking a queue and building it as follows :
eg : if the tree is

                            1
                          /   \
                        2       3
                      /   \    
                    4      5

Then we make the queue as following :

 1-> NULL -> 2 -> 3 -> NULL -> 4 -> 5 -> NULL

Now all we have to do is just connect them, here is the code :

#define node TreeLinkNode
void Solution::connect(TreeLinkNode* root) 
{
    if(root==NULL) return ;
    queue<node *> q;
    q.push(root);
    q.push(NULL);
    while(!q.empty())
    {
        node *temp=q.front();
        q.pop();
        if(temp) temp->next=q.front();
        else { if(!q.empty()) q.push(NULL); } 
        if(temp)
        {
            if(temp->left) q.push(temp->left);
            if(temp->right) q.push(temp->right);
        }
    }
}
#2

I guess you didn’t get the question. It says use constant space and your solution uses queue to build the links which is linear space hence wrong. Although you got the output right it is not a correct solution.

#3

Bro can you pls explain when this :-
else { if(!q.empty()) q.push(NULL); }
condition will occur?