{x}
blog image

Populating Next Right Pointers in Each Node II

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.

Solution Explanation for Populating Next Right Pointers in Each Node II

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.

Solution 1: BFS Approach

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:

  1. Initialization: If the root is null, return null. Create a queue q and enqueue the root.
  2. Level Traversal: While the queue is not empty:
    • Create a temporary variable p to store the previous node (initialized to null).
    • Iterate through the nodes currently in the queue (the number of nodes in a level is obtained using len(q) or q.size()).
    • For each node:
      • If p is not null, link p.next to the current node.
      • Update p to be the current node.
      • Enqueue the left and right children of the current node (if they exist).
  3. Return: The root of the modified tree.

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.

Solution 2: Space-Optimized Approach

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:

  1. Initialization: node points to the root, prev and next are initialized to null.
  2. Outer Loop (Level Traversal): While node is not null:
    • prev and next are reset to null at the beginning of each level.
    • Inner Loop (Nodes at the current level): While node is not null:
      • A helper function 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.
  3. Return: The modified 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.