• 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

The goal is to turn each level of the tree into a left-to-right chain. The level-by-level walk from Binary Tree Level Order Traversal already produces nodes in exactly that order, so a first solution writes itself: process a level, and point each node's next at whichever node the queue hands over after it, leaving the last one null.

while queue:
    n = len(queue)
    for i in range(n):
        node = queue.popleft()
        if i < n - 1:
            node.next = queue[0]        # the next node in this level, still queued
        if node.left:  queue.append(node.left)
        if node.right: queue.append(node.right)

That is correct and runs in O(N) time. Its cost is the queue, which on this tree holds an entire level — up to about N/2 nodes. The real question is whether we can do it with no extra structure at all.

Here is the observation that removes the queue. Once a level has been fully stitched, that level is a linked list. You can stand on its leftmost node and walk rightwards along next pointers, reaching every node of the level in order — without a queue, because the level is now storing its own ordering.

So the algorithm becomes: use the finished level above to walk across, and while walking, stitch the level below. Each level pays for the next one.

Standing on a node curr of the finished level, there are exactly two kinds of link to create beneath it:

The second link is the whole trick, and it is only available because the level we are standing on was stitched during the previous round. The root's level needs no stitching (one node, nothing to its right), which starts the induction off.

leftmost = root
while leftmost and leftmost.left:          # stop when the current 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   # across to the neighbouring parent
        curr = curr.next                   # step sideways using the existing link
    leftmost = leftmost.left               # drop to the start of the level just stitched

The step from 2 to 3 is the one to watch: it moved horizontally along a pointer created in the previous round. Without that, reaching node 3 from node 2 would have required going back up to the root.

Each node is visited once as curr and does constant work, so O(N) time — the same as the queue version. The extra space is two pointers, O(1), down from O(W). Nothing was recomputed; we simply noticed that the output being built was itself a usable structure.

That is the idea worth extracting: 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. It is the same instinct as Morris Traversal, which borrowed the tree's null pointers to remember the way back, and it appears whenever a "build it in place" follow-up shows up. The general question to ask when an interviewer says "now do it in O(1) space" is: what am I storing in that auxiliary structure, and is that information already present, or already being written, somewhere in the data?