Connect All Level Order Siblings (One Continuous Next Chain)

• No level boundaries – the next chain spans the entire tree in BFS order.
• Single previous pointer – one previous pointer persists for the whole traversal, never reset.
• Continuous chain – the last node of level k points to the first node of level k+1.
• Termination – only the very last node of the tree has next = null.
• Complexity – O(n) time, O(w) space for the queue.

What is the Connect All Level Order Siblings problem?

Given a binary tree with an extra next pointer, connect all nodes into one continuous chain in BFS order. Unlike connect-level-order-siblings where each level ends with null, here the last node of each level points to the first node of the next level. Only the very last node of the entire tree has next = null.

How does the BFS solution work?

The solution is nearly identical to connect-level-order-siblings, but with one crucial difference: the previous pointer persists across the entire traversal and is never reset at level boundaries.

package com.bank.service;

import java.util.*;

public class ContinuousChainConnector {

    static class TreeNode {
        int value;
        TreeNode left, right, next;
        TreeNode(int val) { this.value = val; }
    }

    public static void connectAll(TreeNode root) {
        if (root == null) return;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        TreeNode previous = null; // persists across all levels

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (previous != null) {
                previous.next = node;
            }
            previous = node;
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        // previous.next stays null (last node of entire tree)
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(7);

        connectAll(root);

        // Print the chain
        TreeNode current = root;
        StringBuilder chain = new StringBuilder();
        while (current != null) {
            chain.append(current.value);
            if (current.next != null) chain.append(" -> ");
            current = current.next;
        }
        System.out.println(chain.toString());
    }
}

1 -> 2 -> 3 -> 4 -> 5 -> 7

How is this different from connect-level-order-siblings?

The only code difference is whether the previous pointer resets at each level.

| Aspect | Connect Level Siblings | Connect All |
|---|---|---|
| Previous pointer | Reset to null per level | Never reset |
| Level-size snapshot | Required | Not needed |
| Level boundary | Each level ends with null | No level breaks |
| Chain length | Multiple short chains | One long chain |
| Result | Level-by-level linked lists | One BFS-order linked list |

// Connect siblings: reset previous per level
while (!queue.isEmpty()) {
    int levelSize = queue.size();
    TreeNode previous = null; // RESET per level
    for (int i = 0; i < levelSize; i++) { ... }
}

// Connect all: single persistent previous
TreeNode previous = null; // NEVER reset
while (!queue.isEmpty()) {
    TreeNode node = queue.poll();
    if (previous != null) previous.next = node;
    previous = node;
}

Why is the level-size snapshot not needed?

Since there are no level boundaries, you do not need to isolate levels. The BFS loop simplifies to dequeuing one node at a time and linking it. The level-size snapshot is purely for separating levels, which this variant does not require.

// No level-size snapshot needed
while (!queue.isEmpty()) {
    TreeNode node = queue.poll();
    if (previous != null) previous.next = node;
    previous = node;
    // enqueue children
}

What are the edge cases?

- **Null root** – do nothing.
- **Single node** – next stays null (only node in the chain).
- **Left-skewed tree** – chain follows the skew: 1 -> 2 -> 3 -> ... -> n.
- **Perfect binary tree** – chain interleaves levels: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7.

// Edge case: single node
TreeNode single = new TreeNode(42);
connectAll(single);
System.out.println(single.next == null); // true

What are common mistakes?

The most common mistake is accidentally resetting previous per level (writing connect-siblings instead of connect-all).

// WRONG: resetting previous per level (this is connect-siblings, not connect-all)
while (!queue.isEmpty()) {
    int levelSize = queue.size();
    TreeNode previous = null; // BUG: reset per level
    for (int i = 0; i < levelSize; i++) { ... }
}

// CORRECT: persistent previous
TreeNode previous = null;
while (!queue.isEmpty()) {
    TreeNode node = queue.poll();
    if (previous != null) previous.next = node;
    previous = node;
}

What is the time and space complexity?

Time is O(n) because every node is dequeued once. Space is O(w) for the queue. The code is simpler than connect-siblings because the level-size snapshot is not needed.

What should a senior engineer know?

A senior engineer should be able to state the precise difference between connect-siblings and connect-all in one sentence: the previous pointer resets per level for siblings and persists globally for connect-all. They should also recognise that connect-all produces a BFS-order linked list from a tree, which can be useful for sequential processing without revisiting the tree structure.

The follow-up question is often: can you do this in O(1) space? For a perfect tree, the same next-pointer trick from connect-siblings can be adapted, but for a general tree the queue-based approach is necessary.