Populating Next Right Pointers in Each Node II
Problem
next pointer, initially null. Point every node's
next to the node immediately to its right on the same level, or leave
it null if it is the last one. Return the root.[1,2,3,4,5,null,7]Output[1,#,2,3,#,4,5,7,#][]Output[]0 ≤ nodes ≤ 6000 · -100 ≤ Node.val ≤ 100 · Follow-up: O(1) extra space (recursion stack is not counted).
Try it yourself
class Solution {
public Node connect(Node root) {
}
}
next and, as you go, append its children to a new list for the level below
(a dummy head + tail pointer) — no queue needed.Instinct The answer talks about levels, rows, depth order, "closest to the root" or what you see from a side? Queue the tree and process it one level at a time.
Memory hack Freeze the size, drain the row - read n = queue.size() before the loop and one level never bleeds into the next.
Open the Tree BFS (Level Order) guide →Approaches
Brute ForceBFS with Queue
O(n)Space O(w)Level-order traversal with a size snapshot. Within a level, keep the
previously polled node prev and set prev.next = node; the
last node of the level keeps next = null.
public Node connect(Node root) { if (root == null) return null; Queue<Node> queue = new ArrayDeque<>(); queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); Node prev = null; for (int i = 0; i < size; i++) { Node node = queue.poll(); if (prev != null) prev.next = node; prev = node; if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); } } return root; }
Straightforward, but the queue holds a whole level — fails the O(1) follow-up.
BetterDFS with Last-Node-per-Depth
O(n)Space O(h)A left-first pre-order DFS meets the nodes of every level in left-to-right
order. Remember the last node seen at each depth in last; linking
last[d].next = node then chains each level correctly.
public Node connect(Node root) { dfs(root, 0, new ArrayList<>()); return root; } // last.get(d) = most recent node visited at depth d private void dfs(Node node, int depth, List<Node> last) { if (node == null) return; if (depth == last.size()) { last.add(node); // first (leftmost) node of this depth } else { last.get(depth).next = node; last.set(depth, node); } dfs(node.left, depth + 1, last); dfs(node.right, depth + 1, last); }
Only O(h) memory instead of a whole level, but still not constant space.
OptimalWalk Level via next + Dummy Head
O(n)Space O(1)Traverse the current level through its next pointers. A
dummy node heads the next level and tail appends each
existing child, building that level's links. Then jump to
dummy.next and repeat.
public Node connect(Node root) { Node dummy = new Node(0); // dummy.next = head of the next level Node curr = root; while (curr != null) { Node tail = dummy; dummy.next = null; for (; curr != null; curr = curr.next) { // walk current level if (curr.left != null) { tail.next = curr.left; tail = tail.next; } if (curr.right != null) { tail.next = curr.right; tail = tail.next; } } curr = dummy.next; // descend one level } return root; }
Each node touched a constant number of times with just three pointers — meets the follow-up.
At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | BFS with Queue | O(n) | O(w) |
| Better | DFS with Last-Node-per-Depth | O(n) | O(h) |
| Optimal | Walk Level via next + Dummy Head | O(n) | O(1) |
- Assuming a perfect tree (LC 116):
left.next = rightbreaks when children are missing. - Not resetting
dummy.next→ an infinite loop on the last level. - BFS: linking the last node of one level to the first node of the next.
- Start with BFS, then ask: “can the finished level replace the queue?”
- Draw two levels and show
tailstitching children across different parents. - Point out the difference from LC 116 (perfect tree) and why gaps matter.