[LeetCode] #102: Binary Tree Level Order Traversal

Problem:

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

---

Process:

Objective: Returning the values of nodes in the order of level order traversal.

Constraints:
1. The number of nodes in the tree is in the range [0, 2000].
2. -1000 <= Node.val <= 1000

Edge Cases:
1. The tree is empty.
2. The tree is incomplete.

Additional Details:
1. deque.popleft() costs constant time.

---

Solution:

Attempt #1: Counting the number of nodes in each level

• Time Complexity: O(n), where n is the number of nodes
• Space Complexity: O(n), more specifically O(3n)

How it works:
During each level:
1. Append the node value to nodes_in_level list
2. Subtract 1 from the number_of_nodes_in_level to keep track of how many nodes of that specific level are left.
3. Add child nodes into the nodes_to_visit queue.

When you are done with the nodes in one level:
1. Append the nodes_in_level list to the values_list to store the values of that level into the final list that will be returned.
2. Refresh the nodes_in_level list to be empty and number_of_nodes_in_level to be 0.

from collections import deque

def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        values_list = []
        number_of_nodes_in_level = 1
        nodes_in_level = []
        nodes_to_visit = deque([root])
        
        # If the tree is empty
        if not root:
            return []
        
        while nodes_to_visit:         
            node = nodes_to_visit.popleft()
            
            # Adding the node value to nodes_in_level
            nodes_in_level.append(node.val)
            number_of_nodes_in_level -= 1
            
            # Adding children to nodes_to_visit queue
            if node.left:
                nodes_to_visit.append(node.left)
            if node.right:
                nodes_to_visit.append(node.right)
                
            # If nodes in one level is cleared
            if number_of_nodes_in_level == 0:
                values_list.append(nodes_in_level)
                
                # Re-initializing for next level
                number_of_nodes_in_level = len(nodes_to_visit)
                nodes_in_level = []
            
        return values_list

Limitations:
1. It costs too much space.

---

LeetCode Question #102