Binary Tree Level Order Traversal | Leetcode 102

Welcome to the definitive guide on Binary Tree Level Order Traversal (Leetcode 102). If you ever need to analyze a tree exactly layer by layer rather than plunging all the way down to a leaf first, this question is the gold standard for mastering Level-Order strategies.

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: root = [3, 9, 20, null, null, 15, 7] Output: [[3], [9, 20], [15, 7]] (The root 3 is level 0. The children 9, 20 are level 1. The graphical children 15, 7 are level 2).

Approach 1: Iterative Breadth-First-Search (BFS)

Whenever you see the words "level by level", your immediate instinct should jump straight to Breadth-First-Search (BFS). We accomplish this using a First-In-First-Out Data Structure known as a Queue.

The strategy is simple:

1. Push the root into the queue.
2. Enter a while loop that runs as long as the queue is not empty.
3. Crucial Step: Take the size of the queue right now. Since those nodes are precisely the nodes belonging to the current horizontal level, run a fixed for loop exactly size times.
4. On every pop, append the node's value to a temporary level array, and push any of its existing children to the back of the queue.

graph TD
    A["Queue: [Root(3)]"] --> B["Pop 3. Push 9, 20. Appending [3] to Result"]
    B --> C["Queue: [9, 20]"]
    C --> D["Pop 9. No Children. Array: [9]"]
    D --> E["Pop 20. Push 15, 7. Array: [9, 20]"]
    E --> F["Appending [9, 20] to Result"]
    F --> G["Queue: [15, 7]"]
    
    style B fill:#4CAF50,stroke:#fff,stroke-width:2px,color:#fff

# 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
from collections import deque

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        res = []
        if not root: return res
        
        q = deque([root])
        
        while q:
            # How many nodes physically exist on this current level?
            level_length = len(q)
            level = []
            
            for i in range(level_length):
                node = q.popleft()
                level.append(node.val)
                # Enqueue the next level children into the back of the queue
                if node.left: q.append(node.left)
                if node.right: q.append(node.right)
                
            res.append(level)
            
        return res

Complexity Analysis

Approach 2: Recursive Depth-First-Search (DFS)

It blew my mind when I realized that we could generate a horizontal Level Order array using vertical DFS recursion!

If we pass a depth tracking variable into our recursive helper, we can index directly into our master 2D Array List. If the array list's length is equal to our current physical depth, we dynamically spawn a new empty horizontal row for our level.

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        res = []
        
        def dfs(node, depth):
            if not node: return
            
            # Sub-graph hit a brand new level depth! Spawn a new row!
            if len(res) == depth:
                res.append([])
                
            # Insert this node into its respective horizontal row coordinate
            res[depth].append(node.val)
            
            dfs(node.left, depth + 1)
            dfs(node.right, depth + 1)
            
        dfs(root, 0)
        return res

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (102)