Given a perfect binary tree, set each node's next pointer to its right neighbor at the same level (null for the rightmost node). Initially all next pointers are null.

Engineering takeaway. Most people reach for level-order BFS here — a queue, O(n) extra space. There's a subtler way: if you recurse right-to-left, every node already knows the most recent node seen at its level, so the next pointer is just "the last node I recorded for this level." Same O(n) time, only O(h) space.

Intuition

The perfect-tree guarantee gives us a shortcut: every internal node has both children, so we only ever need to check right. And by visiting children right first, we fill the "latest node at each level" map in the correct order — so when we get to a node, next is simply whatever was stored last for its level.

Approach

  1. Recursively traverse the tree, tracking the current level.
  2. Store the latest node seen at each level in a map.
  3. When visiting a node, assign node.next = map[level] (if set), then update map[level] = node.
function connect(root: Node | null): Node | null {
  if (root === null) return null;
 
  const latestByLevel: Record<number, Node> = {};
 
  const traverse = (node: Node, level: number): void => {
    // Perfect tree: process right first so the level map holds the right neighbor
    if (node.right !== null) {
      traverse(node.right, level + 1);
      traverse(node.left, level + 1);
    }
 
    if (latestByLevel[level] !== undefined) {
      node.next = latestByLevel[level];
    }
    latestByLevel[level] = node;
  };
 
  traverse(root, 0);
  return root;
}

The post-order style is key: the next assignment happens after the children are processed, so latestByLevel[level] already points to the right neighbor.

Complexity

  • Time: O(n) — every node visited once.
  • Space: O(h) for the recursion stack (plus the level map, bounded by the number of levels).

The lesson

Level-order isn't the only way to think "level by level." When a problem has a symmetry you can exploit (here, perfect trees + right-first traversal), a small amount of extra thought often removes the queue entirely — and the O(h) space version is the kind of micro-optimization interviewers love to see you reach for.