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:
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.
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) since each node is processed once.
Space Complexity: O(1), only utilizing a few pointers.
| 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. |
Populating Next Right Pointers in Each Node - Leetcode 116 - Python • NeetCode • 49,975 views views
Watch 9 more video solutions →Practice Populating Next Right Pointers in Each Node II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor