/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
    TreeLinkNode* jump(TreeLinkNode *root, int i, int j) {
        TreeLinkNode* node = root;
        while (i) {
            int half_width = 1 << (i-1);
            if (j < half_width) {
                node = node->left;
            } else {
                node = node->right;
                j -= half_width;
            }
            i--;
        }
        return node;
    }

public:
    void connect(TreeLinkNode *root) {
        TreeLinkNode* node = root;
        int height = 0;
        while (node) {
            height++;
            node = node->left;
        }

        TreeLinkNode* leftmost = root;
        for (int i = 0; i < height; i++) {
            int width = 1 << i;
            TreeLinkNode* last = leftmost;
            for (int j = 1; j < width; j++) {
                node = jump(root, i, j);
                last->next = node;
                last = node;
            }
            last->next = NULL;
            leftmost = leftmost->left;
        }
    }
};