LeetCode classic. Given a binary tree (often described as "perfect" — all leaves at the same level), wire each node's next to its right neighbor at the same level.

     1                1 → null
   /   \            / \
  2     3          2 → 3 → null
 / \   / \        / \ / \
4   5 6   7       4→5→6→7 → null

Approach 1 — BFS with queue

Level-order traversal; within each level, link adjacent nodes:

function connect(root) {
  if (!root) return null;
  const queue = [root];
  while (queue.length) {
    const size = queue.length;
    let prev = null;
    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      if (prev) prev.next = node;
      prev = node;
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    // prev.next implicitly null
  }
  return root;
}

Time O(n), Space O(n) (queue width up to n/2 at the bottom level).

Approach 2 — Use built next pointers (O(1) extra space)

The canonical answer for perfect binary trees: walk level by level, using the next pointers built on the level above to traverse without a queue.

function connect(root) {
  if (!root) return null;
  let leftmost = root;

  while (leftmost.left) {                    // perfect tree: while not at leaves
    let head = leftmost;
    while (head) {
      head.left.next = head.right;           // (1) link within parent
      if (head.next) {                       // (2) link across parents
        head.right.next = head.next.left;
      }
      head = head.next;
    }
    leftmost = leftmost.left;                // next level
  }
  return root;
}

Time O(n), Space O(1) (besides input).

Why this works

For each parent on the current level:

1. Link parent.left.next = parent.right — connect siblings.
2. Link parent.right.next = parent.next.left — connect across parent boundaries (using the next we built one level up).

After processing the level, drop to leftmost.left to start the next level.

Variant — non-perfect tree (LeetCode 117)

If the tree isn't perfect (missing children), the children-linking step is messier — you need to find the first available child of parent.next's descendants. The pattern:

function connect(root) {
  let head = root;
  while (head) {
    let dummy = new Node();        // dummy head of next level
    let tail = dummy;
    for (let node = head; node; node = node.next) {
      if (node.left)  { tail.next = node.left;  tail = tail.next; }
      if (node.right) { tail.next = node.right; tail = tail.next; }
    }
    head = dummy.next;
  }
  return root;
}

Use a dummy head to build the next level's linked list as you walk the current level. Clean and handles any tree shape.

Edge cases

• Empty tree.
• Single node — no next links to set; returns root.
• Lopsided tree (variant 117).

Interview framing

"Two clean approaches. BFS with a queue: level-order traversal, linking nodes in each level — O(n) time, O(n) space. The O(1)-space approach uses the next pointers built on the level above to traverse the next level without a queue: for each parent on the current level, link parent.left.next = parent.right and parent.right.next = parent.next?.left; then drop to leftmost.left for the next level. Works directly on a perfect tree. For a general (non-perfect) tree, walk the current level building the next level's linked list with a dummy-head — same O(1) extra space."