116. Populating Next Right Pointers in Each Node
mediumWire 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 Alex Chen, 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
root = [1,2,3,4,5,6,7][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
root = [][]Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
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
Practice these live with InterviewChamp.AI
Drill Populating Next Right Pointers in Each Node and Trees problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →