We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Binary Tree Level Order Traversal

Difficulty: Medium

Problem Description

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

Key Insights

  • Level order traversal can be achieved using a breadth-first search (BFS) approach.
  • We can utilize a queue data structure to facilitate the BFS, processing nodes level by level.
  • Each level's nodes are collected in a temporary list, which is then added to the final result list.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the binary tree. Each node is processed once. Space Complexity: O(m), where m is the maximum number of nodes at any level in the tree (the width of the tree).

Solution

To solve the problem, we will use a breadth-first search (BFS) approach with a queue. We will enqueue the root node and then iteratively process each level of the tree by:

  1. Determining the number of nodes at the current level.
  2. Dequeueing each node, adding its value to a temporary list, and enqueueing its children (left and right).
  3. After processing all nodes at the current level, we add the temporary list to the final result list.

Code Solutions

from collections import deque

def levelOrder(root):
    if not root:
        return []
    
    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)
        level_nodes = []

        for _ in range(level_size):
            node = queue.popleft()
            level_nodes.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(level_nodes)
    
    return result
← Back to All Questions