Untitled

/*
// 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 { //RECURSIVE IN O(1) space .. bith time O(N)
public:
    
    Node* connect(Node* root) {
        if(root==NULL) return NULL;
        Node* head=root;
        while(head!=NULL){
            Node* dum = new Node(-1);
            Node* tmp=dum;
            while(head!=NULL){
                if(head->left) {
                    tmp->next=head->left; // this action also links the dum variable for the first time it runs dum->next= leftmost child of next level
                    tmp=tmp->next;
                }
                if(head->right){
                    tmp->next=head->right;
                    tmp=tmp->next;
                }
                head=head->next;
            }
            head=dum->next;// initially inside the second while loop dum is initialed and is set to null so if head has no children then dum remains null
        }
        return root;
    }
};


/* 
class Solution { //QUEUE SOLUTION O(N)
public:
    Node* connect(Node* root) { 
        if(root==NULL) return NULL; // seg fault generally suggests this  
        queue<Node*> q;
        q.push(root);
        while(!q.empty()){
            int s=q.size();
            Node* dum= new Node(-1);
            while(s--){
                Node* tmp=q.front(); // getting each nodes of the current level
                q.pop();
                dum->next=tmp;   //using a dummy variable to link the nodes of current level
                dum=tmp;
                if(tmp->left) q.push(tmp->left); //preparing the next level in the queue
                if(tmp->right) q.push(tmp->right);
            }
        }
        return root;
    }