Populating Next Right Pointers in Each Node
The key idea
It is a perfect binary tree, so once a level is fully linked you can walk that level left to right via the next pointers you just set, and use them to stitch the children of the level below for free — no queue needed.
Problem
You are given a perfect binary tree where all leaves are on the same level and every parent has two children. Each node has an extra next pointer that should point to its next right node on the same level. If there is no next right node, next should be set to null.
Initially, all next pointers are null. Populate every next pointer so the tree's levels become singly linked lists from left to right. Return the modified tree's root.
The rightmost node on each level has no node to its right, so its next stays null. The challenge is to wire the whole tree using only constant extra space — the next pointers you set on one level give you a free way to traverse it and connect the level below.
Constraints
- The number of nodes in the tree is in the range
[0, 2^12 - 1]. -1000 <= Node.val <= 1000
Examples
Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Input: root = []
Output: []
Complexity
Time: O(n) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More BFS / DFS problems
- 01 MatrixMEDIUM
- Average of Levels in Binary TreeEASY
- Binary Tree Level Order TraversalMEDIUM
- Binary Tree Level Order Traversal IIMEDIUM
- Binary Tree Right Side ViewMEDIUM
- Binary Tree Zigzag Level Order TraversalMEDIUM
- Find Bottom Left Tree ValueMEDIUM
- Find Largest Value in Each Tree RowMEDIUM
- Flood FillEASY
- Keys and RoomsMEDIUM
- Max Area of IslandMEDIUM
- Maximum Level Sum of a Binary TreeMEDIUM