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 problem involves populating the next
pointers of a binary tree's nodes such that each node points to its next right sibling at the same level. Unlike the similar problem where the tree is perfect, this tree can be imperfect (nodes may have only one child or no children).
Two solutions are presented here: one using Breadth-First Search (BFS) and another optimizing space complexity.
This solution uses a queue to perform a level-order traversal of the binary tree. The key idea is to process each level independently. For each level, we iterate through the nodes and link their next
pointers sequentially.
Algorithm:
q
and enqueue the root.p
to store the previous node (initialized to null).len(q)
or q.size()
).p
is not null, link p.next
to the current node.p
to be the current node.Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited and processed exactly once.
Space Complexity: O(N), where N is the number of nodes in the tree. In the worst case (a complete binary tree), the queue can hold up to N/2 nodes.
This approach avoids using a queue and achieves constant space complexity. It uses two pointers: prev
(to keep track of the previously processed node) and next
(to find the first node of the next level).
Algorithm:
node
points to the root, prev
and next
are initialized to null
.node
is not null
:
prev
and next
are reset to null
at the beginning of each level.node
is not null
:
modify
is used to connect nodes efficiently.modify
handles null checks and updates prev
and next
.node
advances to the next node at the current level using node.next
.node
is updated to next
to move to the next level.root
.Time Complexity: O(N), similar to the BFS approach.
Space Complexity: O(1), constant extra space is used. The recursion depth in the modify
function is limited by the height of the tree (log N for balanced trees, but can be N in the worst-case scenario of a skewed tree). However, this space is considered implicit stack space and doesn't count toward the extra space complexity in this problem's constraints.
The provided code examples demonstrate both solutions in Python, Java, C++, Go, TypeScript, and C#. The BFS solution is simpler to understand, but the space-optimized solution is more efficient in terms of memory usage for large trees. Choose the solution that best fits your needs and coding style.