Populating Next Right Pointers in Each Node

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        //Kind of morris traversal - Itretive approach
        // if(root == NULL) return NULL;
        // Node* pre=root;
        // Node* curr=NULL;

        // while(pre->left){
        //     curr=pre;
        //     while(curr){
        //         //connects the left subtree of same level 
        //         //with right subtree of that same level 
        //         curr->left->next = curr->right;

        //         //connect the rightmost node of a level 
        //         //to the leftmost node of the next level.
        //         if (curr -> next) curr->right->next = curr->next->left;

        //         curr = curr->next;
        //     }
        //     pre=pre->left;
        // }
        // return root;

        //Recursive Approach

    //     if(root == NULL) return NULL;

    //     //connects the left subtree of same level 
    //     //with right subtree of that same level 
    //     if(root->left) root->left->next = root->right;

    //     //connect the rightmost node of a level to 
    //     //the leftmost node of the next level.
    //     if(root->right && root->next) root->right->next = root->next->left;

    //     //recursive calls for left and right subtrees.
    //     connect(root->left);
    //     connect(root->right);
    //     return root; 

    // }


    //Using queue
    if (!root)
        return NULL;

    queue<Node*> q;
    q.push(root);

    while (!q.empty())
    {
        int size = q.size();
        while (size--)
        {
            Node* node = q.front();
            q.pop();

            if (size > 0)
                node->next = q.front();

            if (node->left)
                q.push(node->left);

            if (node->right)
                q.push(node->right);
        }
    }
    
    return root;
}
};