Populating Next Right Pointers in Each Node II
Last Updated: March 31, 2026
Understanding the Problem
We have a binary tree where each node has an extra next pointer. Our job is to wire up every node's next to the node immediately to its right on the same level. If a node is the rightmost on its level, its next stays NULL.
The critical difference from LeetCode 116 (Populating Next Right Pointers in Each Node) is that this tree is NOT necessarily perfect. Nodes can be missing anywhere. In a perfect binary tree, the next right node is always predictable: a left child's next is its parent's right child, and so on. Here, we might need to skip over missing children entirely. For example, if a node's parent's sibling has no left child, we need to jump further right to find the next available node.
This makes the problem more interesting because simple parent-child relationships aren't enough. We need a way to traverse across the level efficiently.
Key Constraints:
0 <= number of nodes <= 6000-- With at most 6000 nodes, even O(n^2) would be fast enough. But the follow-up asks for O(1) extra space, which pushes us toward a smarter approach.-100 <= Node.val <= 100-- The values don't matter for this problem. We're only manipulating pointers.- The follow-up explicitly asks for O(1) extra space, which rules out BFS with a queue (O(n) space) and pushes us toward using the
nextpointers themselves to traverse levels.
Approach 1: BFS with Queue (Level-Order Traversal)
Intuition
The most natural way to connect nodes at the same level is to traverse the tree level by level. BFS does exactly that. At each level, we pull out all the nodes, and since they come out left to right, we simply point each node's next to the one that follows it in the queue.
This is the textbook approach and the one most people would reach for first. It works perfectly for any binary tree shape, perfect or not.
Algorithm
- If the root is null, return null immediately.
- Initialize a queue with the root node.
- While the queue is not empty, record the current level's size.
- Process each node in the level. For each node except the last, set its
nextto the node that follows it in the queue. - Add each node's non-null children to the queue for the next level.
- Return the root.
Example Walkthrough
Code
- Time Complexity: O(n). We visit every node exactly once, doing O(1) work per node (connecting
next, enqueuing children). - Space Complexity: O(n). The queue holds at most one full level of nodes. In the worst case (a complete binary tree), the last level has about n/2 nodes, so the queue uses O(n) space.
The BFS approach works, but it stores an entire level of nodes in a queue. For a wide tree, that's O(n) extra space. The follow-up asks: can we do this with O(1) extra space? The key insight is that once we've connected all the next pointers for a level, that level is essentially a linked list we can traverse without a queue.
Approach 2: Constant Space Using Previously Established Next Pointers
Intuition
Here's the core idea: we process the tree one level at a time, top to bottom. After we finish connecting level k, every node on level k is linked via next pointers, forming a linked list. We can then walk across level k using those next pointers, and for each node we visit, we attach its children to a growing linked list that becomes level k+1.
The tricky part is handling the gaps. Since the tree isn't perfect, some nodes might have only a left child, only a right child, or no children at all. We need to skip over those gaps and connect whatever children exist, regardless of which parent they belong to.
A dummy node simplifies this beautifully. We create a dummy node that serves as the head of the "next level" linked list. As we walk across the current level, we append any children we find to the dummy's chain. When we're done with the current level, the dummy's next points to the first node of the next level. Then we move down and repeat.
The trick is that we're using the tree's own structure as a traversal mechanism. Once a level is connected, it becomes a linked list. We iterate over that linked list to build the next level's linked list from the children. No queue needed because the next pointers serve the same purpose.
The dummy node is a classic linked list technique. Without it, we'd need special-case logic to find the first child on the next level (which could be a left child, a right child, or a child of some node further right if earlier nodes have no children). The dummy eliminates all of that: we just append everything to tail, and dummy.next gives us the starting point.
Algorithm
- Start with
currentpointing to the root (level 0 is just the root). - Create a dummy node. This acts as a sentinel for building the next level's linked list.
- Walk across the current level using
nextpointers. For each node, if it has a left child, append it to the tail of the dummy's chain. Same for the right child. - When the current level is fully traversed, the dummy's
nextis the leftmost node of the next level. - Move
currentdown todummy.next, reset the dummy, and repeat. - Stop when there are no more children to process (dummy.next is null).
Example Walkthrough
Code
- Time Complexity: O(n). Each node is visited exactly once (when we process its parent's level and attach it to the next-level chain). The outer loop runs once per level, and the inner loop processes all nodes on that level.
- Space Complexity: O(1). We only use a constant number of pointers:
current,dummy, andtail. The dummy node is a single node, not a growing data structure. No queue, no recursion stack.