Populating Next Right Pointers in Each Node II - Solution & Explanation
Problem Statement
Given a binary tree
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
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.
Example 1:
Input: root = [1,2,3,4,5,null,7] Output: [1,#,2,3,#,4,5,7,#] Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.
Example 2:
Input: root = [] Output: []
Constraints:
- The number of nodes in the tree is in the range
[0, 6000]. -100 <= Node.val <= 100
Follow-up:
- You may only use constant extra space.
- The recursive approach is fine. You may assume implicit stack space does not count as extra space for this problem.
Approach Overview
Problem Overview: You are given a binary tree where each node contains an extra next pointer. The task is to connect every node to its immediate neighbor on the same level. If there is no neighbor, the next pointer should be set to null. Unlike the simpler version of the problem, the tree is not guaranteed to be perfect, so children may appear in any structure.
Approach 1: Level Order Traversal Using a Queue (O(n) time, O(n) space)
This approach performs a standard Breadth-First Search level traversal. Push the root into a queue, then process nodes level by level. For each level, iterate through the nodes currently in the queue and connect the previous node's next pointer to the current node. Children of the current node are pushed into the queue so the next level can be processed afterward. Because every node is visited exactly once, the time complexity is O(n). The queue may hold up to the maximum width of the tree, giving O(n) worst-case space complexity.
This method is straightforward and mirrors how levels are naturally processed in a binary tree. It is often the first solution developers implement because the logic is simple: track the previous node in the level and link it to the current one.
Approach 2: Using Constant Space (Two Pointers) (O(n) time, O(1) extra space)
The optimized solution eliminates the queue by using the already established next pointers to traverse levels. Maintain two pointers: one for scanning the current level and another for building the next level. A temporary dummy node acts as the head of the next level while a tail pointer attaches children as they are discovered.
Start with the root as the current level. Iterate through nodes using their next pointers. Whenever a node has a left or right child, attach it to the tail of the next-level chain and advance the tail pointer. Once the current level is finished, move to dummy.next, which represents the start of the next level, and repeat the process.
This technique effectively performs a level traversal without extra storage. Each node is processed once, so the time complexity remains O(n). Since only a few pointers are used regardless of tree size, the auxiliary space complexity is O(1). The idea resembles pointer-based traversal patterns often seen in DFS style tree problems, but applied level-by-level.
Recommended for interviews: Start with the queue-based BFS explanation because it clearly demonstrates how level connections work. Then transition to the constant-space two-pointer approach. Interviewers typically expect the O(1) extra space solution since it shows strong understanding of pointer manipulation and tree traversal patterns.
Approach 1: Approach 1: Level Order Traversal Using a Queue
This approach uses a breadth-first search (BFS) strategy by employing a queue to keep track of nodes at the current level and connect their children nodes from left to right. After processing all nodes on a level, we move to the children (if any), ensuring the next pointers are correctly set.
This code first checks if the tree is empty and returns immediately if so. It initializes a queue to store nodes. For each node processed, the code sets the next pointer to the next node in the level (or NULL if it is the last node). The children of each node are enqueued for processing in the next level.
Complexity
Time Complexity: O(n), where n is the number of nodes in the tree since each node is enqueued and dequeued once.
Space Complexity: O(n) for the queue in the worst case where the last level of the tree has a maximum number of nodes.
Approach 2: Approach 2: Using Constant Space (Two Pointers)
This approach leverages a two-pointer or head-tail strategy to eliminate the need for extra storage space beyond two pointers. The idea is to work with two nested loops; an outer loop goes level by level, and an inner loop connects nodes within the same level by their next pointers.
This C approach uses an iterative strategy that does not require a queue. Instead, it uses head to signify the current level's starting node and a pair of pointers, nextHead and prev, to indicate the next level's starting point and moving connector.
Complexity
Time Complexity: O(n) since each node is processed once.
Space Complexity: O(1), only utilizing a few pointers.
Approach 3: BFS
We use a queue q for level order traversal. Each time we traverse a level, we connect the nodes of the current level in order.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
Approach 4: Space Optimization
The space complexity of Solution 1 is relatively high because it requires a queue to store the nodes of each level. We can implement it with constant space.
We define two pointers prev and next, which point to the previous node and the first node of the next level, respectively. When traversing the nodes of the current level, we string the nodes of the next level together and find the first node of the next level. After the current level is traversed, we assign the first node next of the next level to node and continue to traverse.
The time complexity is O(n), where n is the number of nodes in the binary tree. The space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Level Order Traversal Using a Queue | Time Complexity: O(n), where n is the number of nodes in the tree since each node is enqueued and dequeued once. |
| Approach 2: Using Constant Space (Two Pointers) | Time Complexity: O(n) since each node is processed once. |
| BFS | — |
| Space Optimization | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Level Order Traversal Using Queue | O(n) | O(n) | Best when clarity matters. Easy to implement and reason about during interviews. |
| Constant Space Two-Pointer Traversal | O(n) | O(1) | Preferred in interviews when minimizing auxiliary space is required. |
Video Solution
Populating Next Right Pointers in Each Node II | Live Coding with Explanation | Leetcode - 117 • Algorithms Made Easy • 27,361 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Populating Next Right Pointers in Each Node II easy or hard?
Populating Next Right Pointers in Each Node II Python/Java solution
How to solve Populating Next Right Pointers in Each Node II in O(n)?
What is the best approach for Populating Next Right Pointers in Each Node II?
Is Populating Next Right Pointers in Each Node II asked at Google/Amazon/Meta?
What data structure is used in Populating Next Right Pointers in Each Node II?
What is the time complexity of Populating Next Right Pointers in Each Node II?
Ready to solve this problem?
Practice Populating Next Right Pointers in Each Node II with our built-in code editor and test cases.
Practice on FleetCode