117.Populating_Next_Right_Pointers_in_Each_Node_II(Medium).md

117. Populating Next Right Pointers in Each Node II (Medium)

Date and Time: Nov 5, 2024, 12:00 (EST)

Link: https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/

Question:

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

Walk-through:

1. Use deque[] to save each level's nodes by running BFS.

2. Then after we pop() the node from deque[], we check if current deque[] is empty or not, if not empty, we set current node's next to be the top of deque.

3. Lastly, we first check if the last node is not None, then we set its next to be None.

Python Solution:

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        # Run BFS on each level
        # If we have two nodes in deque, set the first one to the another one
        # set the last node's next on each level to be None

        # TC: O(n), SC: O(1)
        deque = collections.deque()
        deque.append(root)
        while deque:
            for _ in range(len(deque)):
                node = deque.popleft()
                if node:
                    if node.left:
                        deque.append(node.left)
                    if node.right:
                        deque.append(node.right)
                    if deque:
                        node.next = deque[0]
            # Set None for every outer node (last node in current level)
            if node:
                node.next = None
                
        return root

Time Complexity: $O(n)$, we iterate through all the node, which is n.
Space Complexity: $O(1)$, in this case the deque is constant extra space, because it is given in the question.