struct TreeLinkNode {
    int val;
    TreeLinkNode *left, *right, *next;
    TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
};

void connect(TreeLinkNode *root) {
    TreeLinkNode *p = root; //pointer to go over each nodes level by level
    TreeLinkNode *nextFirst = NULL; //pointer that pointer to first node in next level
    TreeLinkNode **q = &nextFirst; //pointer that keep previous node that will go to link to next

    while(p != NULL) {
        //link all children nodes of current level
        if (p->left) {
            *q = p->left;
            q = &(p->left->next);
        }

        if (p->right) {
            *q = p->right;
            q = &(p->right->next);
        }

        p = p->next;

        //done for this level, go to next level
        if (p == NULL) {
            p = nextFirst;
            nextFirst = NULL;
            q = &nextFirst;
        }
    }
}