Coding Interview PatternsPopulating Next Right Pointers in Each Node II
MediumTree Breadth-First Search

Populating Next Right Pointers in Each Node II

Explanation & Solution

Practice Problem

Description

Given a binary tree (not necessarily perfect), populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to null.

The tree node has the following definition:

`

function Node(val, left, right, next) {

this.val = val;

this.left = left;

this.right = right;

this.next = next;

}

`

Initially, all next pointers are set to null.

Examples

Example 1:

```tree

[1, 2, 3, 4, 5, null, 7]

`

Input:root = [1, 2, 3, 4, 5, null, 7]
0
1
1
2
2
3
3
4
4
5
5
null
6
7

Output: [1, #, 2, 3, #, 4, 5, 7, #]

Explanation: Node 2's next points to 3. Node 4's next points to 5, and 5's next points to 7 (skipping the missing node).

Input: root = []

Output: []

```tree

[1, 2, 3, 4, 5, null, 7, 8]

`

Input:root = [1, 2, 3, 4, 5, null, 7, 8]
0
1
1
2
2
3
3
4
4
5
5
null
6
7
7
8

Output: [1, #, 2, 3, #, 4, 5, 7, #, 8, #]

Constraints

  • The number of nodes in the tree is in the range [0, 6000]
  • -100 <= Node.val <= 100

Approach

Tree Breadth-First Search pattern

1. Base Case

  • If root is null:
  • Return null
  • Reason:
  • An empty tree has no nodes to connect

2. Initialize BFS

  • Create a queue initialized with the root node

3. Process Level by Level

  • While the queue is not empty:
  • Record the current levelSize
  • Loop levelSize times:
  • Dequeue the front node
  • If this is not the last node in the level (i < levelSize - 1):
  • Set node.next = queue[0]
  • If this is the last node in the level:
  • Set node.next = null
  • Enqueue left child if it exists
  • Enqueue right child if it exists

4. Difference from Perfect Binary Tree Version

  • The BFS approach is identical to the perfect binary tree version
  • BFS naturally handles missing children — it only enqueues nodes that exist
  • Nodes at the same level are still adjacent in the queue regardless of tree shape
  • A node like 5 will have its next set to 7 even though 6 is missing, because only existing nodes are in the queue

5. Return the Root

  • All next pointers are now correctly set
  • Return the modified root

Key Insight

  • BFS with level-size tracking works for any binary tree, not just perfect ones
  • The queue only contains existing nodes, so gaps in the tree are naturally skipped
Time
O(n)visit each node once
Space
O(n)for the queue

Visualization

Input:
DFS Traversal[1, 2, 3, 4, 5, 7]
123457
output0

Press play to start DFS traversal

CurrentIn stackComplete
13 steps

Solution Code

Previous
Populating Next Right Pointers in Each Node
Next
Symmetric Tree