MediumNeetCode150Linked ListTreeDepth-First SearchBreadth-First SearchBinary Tree
Populating Next Right Pointers in Each Node
Connect nodes at same level.
Examples
Input
root = [1,2,3,4,5,6,7]
Output
[1,#,2,3,#,4,5,6,7,#]
Next pointers: 1->null, 2->3, 3->null, 4->5, 5->6, 6->7
Constraints
- •
Number of nodes in [0,2^12-1] - •
-1000 <= Node.val <= 1000
Approaches
Level-order traversal.
CodeT: O(n) | S: O(n) queue
Use next pointers already set.
CodeT: O(n) | S: O(1) space
Use parent's next pointer.
CodeT: O(n) | S: O(log n) stack
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| BFS | O(n) | O(n) queue | Level-order traversal. |
| Level-order + Next Pointers | O(n) | O(1) space | Use next pointers already set. |
| Recursive | O(n) | O(log n) stack | Use parent's next pointer. |
BFS
T: O(n)S: O(n) queue
Level-order traversal.
Level-order + Next Pointers
T: O(n)S: O(1) space
Use next pointers already set.
Recursive
T: O(n)S: O(log n) stack
Use parent's next pointer.
Common Mistakes
Not handling null root
Not connecting across parents
Using extra space unnecessarily