class Solution {
public:
    Node* connect(Node* root) {
        if(root == nullptr) return nullptr;
        queue<Node*> que;
        que.push(root);

        while(!que.empty()) {
            int size = que.size();

            Node* node = que.front();
            if(que.front()->left != nullptr) que.push(que.front()->left);
            if(que.front()->right != nullptr) que.push(que.front()->right);
            que.pop();

            for(int i = 1; i < size; i++){
                node->next = que.front();
                node = que.front();
                if(que.front()->left != nullptr) que.push(que.front()->left);
                if(que.front()->right != nullptr) que.push(que.front()->right);
                que.pop();
                
            }

        }

        return root;
    }
};

class Solution {
public:
    Node* prev;
    Node* leftmost;

    void processChild(Node* childNode) {
        if(childNode != nullptr) {
            if(prev != nullptr) {
                // connect prev to childNode
                prev->next = childNode;
            } else {
                // set new leftmost to next level
                leftmost = childNode;
            }
            // move prev to childNode
            prev = childNode; 
        }
    }

    Node* connect(Node* root) {
        if(root == nullptr) return nullptr;
        
        // left most starts from root
        leftmost = root;
        
        // iterate until there is no leftmost
        while(leftmost != nullptr){
            // iterate this level by curr
            Node* curr = leftmost;
            prev = nullptr;

            // reset leftmost to track next level leftmost
            leftmost = nullptr;

            while(curr != nullptr) {
                processChild(curr->left);
                processChild(curr->right);
                curr = curr->next;
            }
        }

        return root;
    }
};