Skip to main content

116. Populating Next Right Pointers in Each Node

medium

Wire up every node's 'next' pointer to its same-level right neighbor in a perfect binary tree. BFS works in O(width) space — the elegant move is O(1) space using already-established next pointers as your queue.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

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

Constraints

  • The number of nodes in the tree is in the range [0, 2^12 - 1].
  • -1000 <= Node.val <= 1000

Examples

Example 1

Input
root = [1,2,3,4,5,6,7]
Output
[1,#,2,3,#,4,5,6,7,#]

Explanation: Given the perfect binary tree, populate each next pointer to point to its next right node. The serialized output is in level order, with '#' as a level terminator.

Example 2

Input
root = []
Output
[]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

BFS solves it in O(n) time and O(width) space — but the follow-up asks for O(1) extra space.

Hint 2

Because it's a perfect tree, you always have node.left and node.right. Wire node.left.next = node.right.

Hint 3

For the cross-parent connection, use node.next: if node.next is non-null, node.right.next = node.next.left.

Solution approach

Reveal approach

O(1) space using already-set next pointers as a level queue. Walk down the leftmost spine — that's the head of each level. At each level, walk node = head: connect node.left.next = node.right (sibling under same parent); if node.next is non-null, connect node.right.next = node.next.left (cross-parent connection). Move node = node.next. After finishing a level, head = head.left. Stop when head.left is null (last level). Because the tree is perfect, both children always exist where needed. Return root. O(n) time, O(1) extra space. Standard BFS alternative: per-level loop, connect each popped node to the previous popped node in that level — O(width) space.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • tree-bfs
  • tree-dfs
  • linked-list

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Microsoft
  • Bloomberg

More Trees practice problems

See all Trees problems →