Next pointers (Tree BFS Sub-pattern)

// Next pointers in O(1) space: walk the current level through its `next` links
// while building the level below with a dummy head. Works for any shape of tree.
// struct Node { int val; Node *left, *right, *next; };   (given by LeetCode)
Node* connect(Node* root) {
    Node* levelStart = root;
    while (levelStart) {
        Node dummy(0);                            // dummy.next will be the first node of the level below
        Node* tail = &dummy;
        for (Node* cur = levelStart; cur; cur = cur->next) {   // this level is already linked
            if (cur->left)  { tail->next = cur->left;  tail = tail->next; }
            if (cur->right) { tail->next = cur->right; tail = tail->next; }
        }
        levelStart = dummy.next;                  // go down one level
    }
    return root;
}