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

Populating Next Right Pointers in Each Node

Explanation & Solution

Practice Problem

Description

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. 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;

}

`

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.

Initially, all next pointers are set to null.

Examples

Example 1:

```tree

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

`

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

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

Explanation: The # symbols represent the end of each level (where next is null). Node 2's next points to 3, node 4's next points to 5, 5's next points to 6, and 6's next points to 7.

Input: root = []

Output: []

```tree

[1, 2, 3]

`

Input:root = [1, 2, 3]
0
1
1
2
2
3

Output: [1, #, 2, 3, #]

Constraints

  • The number of nodes in the tree is in the range [0, 4096]
  • -1000 <= Node.val <= 1000
  • The tree is a perfect binary tree

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] (the next node to be processed is the right neighbor)
  • If this is the last node in the level:
  • Set node.next = null
  • Enqueue left and right children if they exist

4. Why This Works

  • After dequeuing a node and before moving to the next iteration, we've already enqueued its children
  • But the key insight is: for nodes within the same level, when we dequeue node i, queue[0] is node i+1 at the same level (since we haven't finished the level loop yet)
  • The last node in each level correctly gets next = null

5. Return the Root

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

Key Insight

  • BFS naturally processes nodes level by level
  • Within a level, after dequeuing a node, the front of the queue is its right neighbor at the same level
Time
O(n)visit each node once
Space
O(n)for the queue

Visualization

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

Press play to start DFS traversal

CurrentIn stackComplete
15 steps

Solution Code

Previous
Binary Tree Level Order Traversal II
Next
Populating Next Right Pointers in Each Node II