Populating Next Right Pointers in Each Node II
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 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, a node and the node to its right can belong to different parents, with gaps in between. If the parent of a node has no children but the next parent does, the connection has to skip across to that further parent's children.
Simple parent-child relationships are not enough. The solution needs a way to traverse across an entire level regardless of which parent each node descends from.
Key Constraints:
0 <= number of nodes <= 6000. The follow-up asks for O(1) extra space, which rules out BFS with a queue (that queue holds up to a full level, so O(n) space).-100 <= Node.val <= 100. Values are irrelevant here; the algorithm only rewires pointers.- The empty tree (
[]) is a valid input, so the code must handle a null root before touching any pointer.
Approach 1: BFS with Queue (Level-Order Traversal)
Intuition
To connect nodes on the same level, traverse the tree level by level. BFS does this directly. Process one level at a time: the nodes come off the queue in left-to-right order, so each node's next is the node that follows it within the same level. The last node on a level has no successor, so its next stays null.
This works for any binary tree shape, perfect or not, because BFS groups nodes by depth regardless of which parent they came from.
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.
BFS stores an entire level of nodes in a queue, which is O(n) extra space for a wide tree. The follow-up asks for O(1) extra space. The next approach removes the queue by observing that once a level's next pointers are connected, that level is already a linked list that can be traversed top to bottom without any auxiliary storage.
Approach 2: Constant Space Using Previously Established Next Pointers
Intuition
Process the tree one level at a time, top to bottom. Once level k is fully connected, its nodes form a linked list through their next pointers. Walk across that list, and for each node, append its children to a separate linked list that becomes level k+1. The connected level serves as the iterator for building the level below it, so no queue is required.
Handling the gaps is the part that needs care. Because the tree is not perfect, a node may have only a left child, only a right child, or none. The children of consecutive nodes on level k might belong to different parents and still be adjacent on level k+1. The build step ignores parentage entirely: it appends whatever children exist, in the order they are encountered, and adjacency falls out automatically.
A dummy node makes the build step uniform. It serves as the fixed head of the next level's list, with a tail pointer tracking the last node appended so far. Every child found is attached after tail, whether it is the first child of the level or the tenth. After the whole level is processed, dummy.next points to the leftmost node of the next level, which becomes the new starting point.
The connection is correct because of the order children are appended. Walking level k left to right and, at each node, appending its left child before its right child visits level k+1's nodes in exact left-to-right order. Linking each to the previous one (via tail) reproduces the same left-to-right next chain BFS would produce.
Without the dummy, the first child on a level would need special-case handling, since it can be a left child, a right child, or a child of a node further right when earlier nodes have none. Appending to tail starting from a dummy removes that special case: the first append sets dummy.next, and the rest extend the chain.
Algorithm
- Start with
currentpointing to the root (level 0 is the root alone). - While
currentis not null, begin a new level: create a fresh dummy node and settailto it. - Walk across the current level using
nextpointers. At each node, if it has a left child, attach it aftertailand advancetail. Do the same for the right child. - When the current level is fully traversed,
dummy.nextis the leftmost node of the next level (or null if the current level had no children). - Set
currenttodummy.nextand repeat from step 2. - The outer loop ends when
currentis null, meaning the last processed level had no children.
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.