Watch 10 video solutions for Populating Next Right Pointers in Each Node II, a medium level problem involving Linked List, Tree, Depth-First Search. This walkthrough by NeetCode has 49,975 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
[0, 6000].-100 <= Node.val <= 100
Follow-up:
Problem Overview: Each node in a binary tree has a next pointer that should point to its immediate neighbor on the same level. If no neighbor exists, the pointer should be null. The tree is not guaranteed to be perfect, so missing children must be handled while linking nodes level by level.
Approach 1: Level Order Traversal Using a Queue (O(n) time, O(n) space)
This approach performs a classic level order traversal using a queue, which is the most straightforward application of Breadth-First Search. Push the root into a queue and process nodes level by level. For each level, iterate through all nodes currently in the queue and connect each node's next pointer to the next node in the iteration. The final node in the level points to null. This method is easy to reason about and works for any binary tree structure, but the queue stores up to an entire level of nodes, giving it O(n) auxiliary space.
Approach 2: Using Constant Space (Two Pointers) (O(n) time, O(1) space)
This method links nodes while traversing the tree level by level using already established next pointers. Maintain two pointers: one that scans the current level and another that builds the next level. As you iterate across the current level using next, attach each child (left then right) to a running tail pointer representing the next level chain. A dummy head node often simplifies this process by providing a fixed start for the next level. Once the current level is fully processed, move to the next level using the dummy's next pointer. This technique avoids extra memory and demonstrates deeper understanding of pointer manipulation in tree traversal.
Recommended for interviews: Start with the queue-based BFS since it clearly shows the level-by-level relationship between nodes. Interviewers typically expect the constant-space solution afterward. The two-pointer technique proves you understand how to reuse the next links to traverse levels without allocating additional memory.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Level Order Traversal Using Queue | O(n) | O(n) | Best for clarity and quick implementation. Useful when extra memory for a queue is acceptable. |
| Constant Space Two-Pointer Traversal | O(n) | O(1) | Preferred in interviews when asked to avoid additional space. Works by reusing established next pointers. |