Populating Next Right Pointers II

Populating Next Right Pointers in Each Node II

Given a binary tree where each node has an additional next pointer (initially set to null), 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.

The tree is not necessarily a perfect binary tree.

Examples

Example 1:

Input: root = [1, 2, 3, 4, 5, null, 7]
Output: [1, #, 2, 3, #, 4, 5, 7, #]
Explanation: '#' represents null next pointers.

      1 -> null
     / \
    2 -> 3 -> null
   / \    \
  4-> 5 -> 7 -> null

Example 2:

Input: root = []
Output: []

Constraints

• The number of nodes in the tree is in the range [0, 6000].
• -100 <= Node.val <= 100

Expected Complexity

• Time: O(n)
• Space: O(n) for BFS, O(1) for iterative with next pointers