🌴102. Binary Tree Level Order Traversal

Medium | Grind 75 | September 28th Wednesday, 20

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

Constraints:

• The number of nodes in the tree is in the range [0, 2000].

• -1000 <= Node.val <= 1000

Example 1

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Example 2

Input: root = [1]
Output: [[1]]

Example 3

Input: root = []
Output: []

SOLUTION

We use a queue to traverse the nodes. We first add the root node to the "queue" and then loop through it. For each node in the queue, we check if an element in the output list from the same level exists. If there is, the node's value is appended to that list. If not, a new list is created in the output list with the node's value. We then add the children of the current node to the queue and repeat the process until all the nodes are traversed.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        output = []
        if root:
            
            queue = deque()
            
            #add the root node
            queue.append((root,1))
            
            while queue: 
                curr = queue.popleft()
                
                # an element from the same level exist in output
                if curr[1] == len(output): 
                    output[curr[1]-1].append(curr[0].val)
                
                # first element from the current level
                else: 
                    output.append([curr[0].val])
                
                
                next_level = curr[1]+1
                if curr[0].left: 
                    queue.append((curr[0].left, next_level))
                
                if curr[0].right: 
                    queue.append((curr[0].right, next_level))
            
        
        
        return output
        

TIME AND SPACE COMPLEXITY

TIME: O(n) where n is the number of nodes. We traverse all the nodes once in the tree.

SPACE: O(n) at the maximum, our queue will contain n number of nodes. Additionally, our output list will also contain n number of nodes.