Binary Tree Level Order Traversal medium

Problem Statement

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).

Example 1

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

Example 2

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

Steps

1. Initialization: Create an empty list result to store the level order traversal. Initialize a queue queue with the root node.
2. Level Traversal: While the queue is not empty:
   • Get the size level_size of the queue. This represents the number of nodes at the current level.
   • Create an empty list level to store the values of nodes at the current level.
   • Iterate level_size times:
     • Dequeue a node from the queue.
     • Append the node's value to the level list.
     • If the node has a left child, enqueue the left child.
     • If the node has a right child, enqueue the right child.
   • Append the level list to the result list.
3. Return: Return the result list.

Explanation

The algorithm uses Breadth-First Search (BFS) to traverse the binary tree level by level. The queue acts as a FIFO (First-In, First-Out) structure, ensuring that nodes at the same level are processed before moving to the next level. The level_size variable is crucial for processing nodes at each level separately, thus ensuring that each level's nodes are correctly grouped in the output.

Code

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def levelOrder(root):
    """
    :type root: TreeNode
    :rtype: List[List[int]]
    """
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)
        level = []
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)

    return result


#Example usage
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)

print(levelOrder(root)) # Output: [[3], [9, 20], [15, 7]]

root = TreeNode(1)
print(levelOrder(root)) # Output: [[1]]

root = None
print(levelOrder(root)) # Output: []

Complexity

• Time Complexity: O(N), where N is the number of nodes in the binary tree. Each node is visited and processed exactly once.
• Space Complexity: O(W), where W is the maximum width of the binary tree. In the worst case (a complete binary tree), W can be equal to N, making the space complexity O(N). This is due to the queue storing nodes at each level. In the best case (a perfectly balanced tree), W is proportional to log(N), resulting in a space complexity of O(log N).