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 = NULL; //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) { // we don't need to do check if the tree is full tree
            if (q == NULL) {
                nextFirst = p->left;
                q = p->left;
            } else {
                q->next = p->left;
                q = q->next;
            }
        }

        if (p->right) { // we don't need to do check if the tree is full tree
            if (nextFirst == NULL) {
                nextFirst = p->right;
                q = p->right;
            } else {
                q->next = p->right;
                q = q->next;
            }
        }

        p = p->next;

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