Binary Tree Level Linking

Description

Level linking fills in each node's next pointer so it points at the node to its right on the same level, or null at the level's end. A BFS queue does it directly, but holds a whole level at once. The O(1)-space trick builds each level's links while walking the level above it, which is already linked, using a dummy node to collect the next level's chain.

We'll go from simple to more technical:

1. The pattern: walk a linked level, chain the level below behind a dummy.
2. A second flavor: the shortcut for perfect trees.
3. Where sibling pointers pay off (database indexes).
4. The shape assumptions that break, and when a queue is simply fine.

The approach

With a queue you'd take one level at a time and link its nodes left to right. But the queue holds a whole level, about n/2 nodes in a full tree. Here's the O(1)-space idea. Once a level is linked, its next pointers already form a path across it. So walk that path, and as you pass each node, attach its children to a chain for the level below. A dummy node starts the chain, so the first child needs no special case. When the walk ends, dummy.next is the first node of the level below.

The last level is linked 1 -> 9, across two different parents. Note that 3 has no left child, so "the next level starts at levelStart.left" would have been wrong.

Node connect(Node root) {
    Node levelStart = root;
    while (levelStart != null) {
        Node dummy = new Node(0);   // placeholder - dummy.next ends up as the next level's first node
        Node tail = dummy;
        Node cur = levelStart;
        while (cur != null) {                          // walk the current level via its own next pointers
            if (cur.left != null) { tail.next = cur.left; tail = tail.next; }
            if (cur.right != null) { tail.next = cur.right; tail = tail.next; }
            cur = cur.next;
        }
        levelStart = dummy.next;                        // move down to the level just linked
    }
    return root;
}

def connect(root: Node | None) -> Node | None:
    level_start = root
    while level_start is not None:
        dummy = Node(0)      # placeholder - dummy.next ends up as the next level's first node
        tail = dummy
        cur = level_start
        while cur is not None:                     # walk the current level via its own next pointers
            if cur.left is not None:
                tail.next = cur.left
                tail = tail.next
            if cur.right is not None:
                tail.next = cur.right
                tail = tail.next
            cur = cur.next
        level_start = dummy.next                   # move down to the level just linked
    return root

The dummy is the same trick as in linked-list merging: tail always has somewhere to attach.

A second flavor: a perfect tree needs no dummy

In a perfect tree, every internal node has two children and every leaf is at the same depth. Then each level is fully predictable, and two links per node do the whole job:

Node connect(Node root) {
    Node levelStart = root;
    while (levelStart != null && levelStart.left != null) {
        Node cur = levelStart;
        while (cur != null) {
            cur.left.next = cur.right;                             // siblings under the same parent
            if (cur.next != null) cur.right.next = cur.next.left;  // across the parent boundary
            cur = cur.next;
        }
        levelStart = levelStart.left;                              // next level starts at the far left
    }
    return root;
}

def connect(root: Node | None) -> Node | None:
    level_start = root
    while level_start is not None and level_start.left is not None:
        cur = level_start
        while cur is not None:
            cur.left.next = cur.right                      # siblings under the same parent
            if cur.next is not None:
                cur.right.next = cur.next.left             # across the parent boundary
            cur = cur.next
        level_start = level_start.left                     # next level starts at the far left
    return root

The first link joins two siblings. The second crosses from one parent's right child to the next parent's left child, found through the parent's own next. Both assume every node has two children, which is why this only works on perfect trees.

Where you'll see it

B+-trees, the index structure behind most relational databases, link the pages on their bottom level with sibling pointers. A range scan walks down to its first key, then moves sideways from page to page instead of climbing back up the tree.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. In the general version, why can't the next level simply start at levelStart.left?

2. The perfect-tree version sets only cur.left.next = cur.right. In [1, 2, 3, 4, 5, 6, 7], what does walking the bottom level through next give?

3. Why is it safe to walk level k through its next pointers while writing level k + 1's?

Key takeaways

• A linked level's next pointers are a path across it. Walking that path replaces the queue, for O(1) extra space.
• In a general tree, a dummy node catches the next level's first node, whoever its parent is.
• A perfect tree needs two links per node: siblings, and across the parent boundary.
• The perfect-tree rule crashes on a missing child. Use it only on trees guaranteed to be perfect.
• The loop reads one level and writes the next, never the same one.