102. Binary Tree Level Order Traversal#

Difficulty: Medium

Link to Problem: To see the Binary Tree Level Order Traversal problem on LeetCode, click here!

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

Solution:#

Here’s a Python function to solve this problem:

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

def levelOrder(root):
    # Check if the tree is empty, if so, return an empty list.
    if not root:
        return []

    # Initialize an empty list to store the result.
    result = []
    
    # Initialize a queue with the root node to perform BFS.
    queue = [root]

    while queue:
        # Initialize an empty list to store the values of nodes at the current level.
        level_values = []
        
        # Get the number of nodes at the current level.
        level_size = len(queue)

        # Iterate through the nodes at the current level.
        for _ in range(level_size):
            # Dequeue the front node from the queue.
            node = queue.pop(0)
            
            # Append the value of the current node to the level_values list.
            level_values.append(node.val)

            # Enqueue the left and right children of the current node if they exist.
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        # Append the level_values list (values at the current level) to the result list.
        result.append(level_values)

    # Return the final result, which is a list of lists representing level order traversal.
    return result

Explanation:#

  1. We define a TreeNode class that represents a node in the binary tree. Each TreeNode object has a value (val) and two child nodes: left and right.

  2. The levelOrder function takes the root of the binary tree as its input and returns the level order traversal of the tree as a list of lists.

  3. We start by checking if the input root is None, which indicates an empty tree. If the tree is empty, we return an empty list because there are no nodes to traverse.

  4. We initialize an empty list called result to store the final result, which will be a list of lists containing node values at each level.

  5. We initialize a queue called queue with the root node. This queue will be used for breadth-first traversal of the tree.

  6. We enter a while loop that continues until the queue is empty. Inside the loop, we perform the following steps:

    • We initialize an empty list called level_values to store the values of nodes at the current level.

    • We determine the number of nodes at the current level by getting the length of the queue. This is done to process nodes level by level.

    • We iterate through the nodes at the current level using a for loop. For each node in the current level:

      • We dequeue (remove) the front node from the queue.

      • We append the value of the dequeued node to the level_values list, effectively collecting the values of nodes at the current level.

      • If the dequeued node has a left child, we enqueue the left child to the queue.

      • If the dequeued node has a right child, we enqueue the right child to the queue.

    • After processing all nodes at the current level, we append the level_values list to the result list. This represents the values at the current level.

  7. The loop continues until all levels have been traversed, and the queue becomes empty.

  8. Finally, we return the result list, which contains lists of node values at each level, representing the level order traversal of the binary tree.

The code effectively performs a breadth-first traversal of the binary tree, processing nodes level by level, and constructs the result list that represents the level order traversal.

Test cases#

# Example 1: 

# Construct the tree
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)

result = levelOrder(root)
print(result)

[[3], [9, 20], [15, 7]]

# Example 2:

# Using the same tree as before
root = TreeNode(1)
result = levelOrder(root)
print(result)

[[1]]

# Example 3:
# Creating a new tree for this example
root = None
result = levelOrder(root)
print(result)

[]

Time and Space Complexity Analysis#

Let’s analyze the time and space complexity of the levelOrder function:

Time Complexity:

The time complexity of this function is O(N), where N is the number of nodes in the binary tree. This is because we visit each node exactly once during the breadth-first traversal.

In the worst case, we have to enqueue and dequeue all nodes in the binary tree, which is proportional to the number of nodes (N). In each level, we process all nodes in that level, and since there are a total of log(N) levels in a balanced binary tree, the time complexity can also be approximated as O(N) for unbalanced trees.

Space Complexity:

The space complexity of this function is O(N), where N is the number of nodes in the binary tree. Here’s how the space complexity breaks down:

  1. The result list stores the level order traversal, and in the worst case, it contains N/2 levels (for a completely unbalanced binary tree). So, the space used by result is O(N).

  2. The queue data structure is used for BFS traversal. In the worst case, it can store all nodes at the last level of the tree. In a balanced binary tree, the maximum number of nodes at any level is 2^(log(N)), which is still O(N). In the case of an unbalanced tree, it can be even worse. So, the space used by queue is O(N).

Overall, the dominant factor in terms of space complexity is the queue, and the space complexity is O(N).

In summary, the function’s time complexity is O(N), and its space complexity is also O(N). It is an efficient and optimal solution for performing a level order traversal of a binary tree.

Challenging Exercises:#

  1. Reverse Level Order Traversal: Modify the levelOrder function to return the level order traversal in reverse order (from bottom to top). For example, if the input tree is [3, 9, 20, null, null, 15, 7], the output should be [[15, 7], [9, 20], [3]].

  2. Zigzag Level Order Traversal: Write a function that performs a level order traversal of a binary tree in a zigzag pattern. In a zigzag traversal, the nodes at even levels are traversed from left to right, and nodes at odd levels are traversed from right to left. For example, if the input tree is [3, 9, 20, null, null, 15, 7], the output should be [[3], [20, 9], [15, 7]].