Skip to main content

🟨 Binary Tree Level Order Traversal (#102)

🔗 Problem Link​

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

💡 Examples​

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: []

🔑 Key Insights & Approach​

Core Observation: Use BFS (queue) to traverse level by level. Process all nodes at current level before moving to next.

Why BFS (Queue)?

  • Natural fit for level order traversal
  • O(n) time, O(n) space
  • Easy to group by level

Approaches:

  1. Iterative BFS with queue: O(n) time, O(n) space - standard
  2. Recursive DFS with level tracking: O(n) time, O(h) space

Pattern: "BFS Level Order Traversal" pattern.

🐍 Solution: Python​

Approach 1: BFS with Queue​

Time Complexity: O(n) | Space Complexity: O(n)

from collections import deque
from typing import Optional, List

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]]:
        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

Approach 2: DFS with Level Tracking​

Time Complexity: O(n) | Space Complexity: O(h)

from typing import Optional, List

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        result = []

        def dfs(node, level):
            if not node:
                return

            # Create new level if needed
            if len(result) == level:
                result.append([])

            result[level].append(node.val)

            dfs(node.left, level + 1)
            dfs(node.right, level + 1)

        dfs(root, 0)
        return result

🔵 Solution: Golang​

Approach: BFS​

Time Complexity: O(n) | Space Complexity: O(n)

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return [][]int{}
    }

    result := [][]int{}
    queue := []*TreeNode{root}

    for len(queue) > 0 {
        levelSize := len(queue)
        level := []int{}

        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]

            level = append(level, node.Val)

            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }

        result = append(result, level)
    }

    return result
}

📚 References​