• The number of nodes is in the range [0, 6000]
• -100 <= Node.val <= 100
• The tree is perfect: every internal node has two children, all leaves share one depth
• The recursion stack does not count against extra space in the follow-up

Turn each level into a left-to-right chain: every node's next points at its right neighbour on the same level, and the rightmost node of each level points at null. The tree is perfect — every internal node has two children, all leaves share one depth.

        1 -> #
       / \
      2 -> 3 -> #
     / \  / \
    4 ->5 ->6 ->7 -> #        (5 -> 6 crosses between different parents)

A queue solves it directly: sweep level by level and point each node's next at whatever comes off the queue after it. Correct, O(N) time — but the queue holds a whole level, up to ~N/2 nodes. Can we do it with no queue at all?

Two kinds of link have to be made on each level. The easy ones are between siblings — two children of the same parent — because we're holding the parent. The hard one is the jump between subtrees, like 5 → 6: those two have different parents (2 and 3), and nothing directly connects them.

Here's the unlock. Suppose the level above is already linked, so 2 → 3. Then from parent 2 we can reach parent 3 for free by following 2.next — and 3's left child is exactly the node that 5 must point to. So we stitch a level by walking across the already-finished level above it, using its next pointers as a walkway.

Standing on parent 2 (with 2.next = 3), we make both links 2's children need:

        2 ---next--> 3
       / \          / \
      4   5 ------> 6   7

   sibling:  4.next = 5                 (2's own two children)
   cross:    5.next = 6  = 2.next.left  (hop to 3, grab its left child)

Then step from 2 to 3 (again via 2.next) and repeat there: 6.next = 7. When next runs out, the level is done — drop to its leftmost child and stitch the next level down.

What starts it all: the root's level is a single node, already trivially "linked," so it serves as the walkway for level 1; level 1 then becomes the walkway for level 2, and so on down.

leftmost = root
while leftmost and leftmost.left:          # stop when the level has no children
    curr = leftmost
    while curr:                            # walk across the finished level
        curr.left.next = curr.right        # siblings
        if curr.next:
            curr.right.next = curr.next.left   # cross to the neighbouring parent
        curr = curr.next                   # step sideways along the existing link
    leftmost = leftmost.left               # drop to the level just stitched

root 1; 1's children 2, 3; 2's children 4, 5; 3's children 6, 7:

level of 1:  link 2 -> 3.  (1.next is null, no cross)      -> 2 -> 3
level of 2:  walk 2 -> 3
   at 2:  4 -> 5 (sibling);  2.next = 3, so 5 -> 3.left = 6 (cross)
   at 3:  6 -> 7 (sibling);  3.next null, no cross
                                             -> 4 -> 5 -> 6 -> 7
drop to 4: 4.left is null -> done

The move to watch is stepping 2 → 3: it slid horizontally along a pointer built the previous round. Without it, reaching 3 from 2 would mean climbing back up to the root.

Each node visited once as curr, constant work: O(N) time, and just two pointers of extra space — O(1), down from the queue's O(W). Nothing recomputed; we just noticed the output being built was itself a usable structure.

The idea to extract: when an algorithm's output is a set of links, check whether the links already written can be used to navigate while writing the rest. Whenever an interviewer says "now do it in O(1) space," ask: what am I storing in that extra structure — and is that information already present, or already being written, somewhere in the data itself?