LeetCode 107 - Binary Tree Level Order Traversal II

The problem asks us to traverse a binary tree and return the node values level by level, but in bottom-up order. Normally, a level order traversal collects values from the root down to the leaves.

leetcodemediumtreebreadth-first-searchbinary-tree

LeetCode Problem 107

Difficulty: 🟡 Medium
Topics: Tree, Breadth-First Search, Binary Tree

Solution

Problem Understanding

The problem asks us to traverse a binary tree and return the node values level by level, but in bottom-up order. Normally, a level order traversal collects values from the root down to the leaves. Here, we need to reverse that order and return the leaf levels first, moving up to the root.

The input is a standard binary tree represented by its root node. Each node contains an integer value and pointers to its left and right children. The output is a list of lists of integers, where each inner list corresponds to a level in the tree, starting from the bottom-most level and moving up to the root.

The constraints specify that the tree can have up to 2000 nodes, and node values range from -1000 to 1000. This suggests that the algorithm should ideally run in linear time relative to the number of nodes. Edge cases include an empty tree (root = None) and trees with only one node.

Approaches

A brute-force approach would perform a standard level order traversal (BFS), storing each level in a list as we go from top to bottom. Once all levels are collected, we could reverse the list of levels at the end. While this works, it uses extra space for the level storage and an additional reverse operation. It is correct but slightly inefficient in terms of space and post-processing.

The key insight for an optimal solution is that we can still perform BFS but prepend each level to the result list as we traverse. This way, the bottom levels naturally end up at the start of the result list, eliminating the need for a separate reverse operation. BFS ensures that we visit nodes level by level, and prepending preserves the bottom-up order efficiently.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Perform BFS top-down and reverse the list at the end
Optimal O(n) O(n) Perform BFS and prepend each level to the result list

Algorithm Walkthrough

  1. Handle edge case: If root is None, return an empty list immediately. This prevents unnecessary processing for empty trees.
  2. Initialize BFS structures: Use a queue to facilitate BFS. Start by enqueuing the root node. Create an empty result list to store levels in bottom-up order.
  3. Process each level: While the queue is not empty, determine the number of nodes in the current level (level_size). Create a temporary list to store values for this level.
  4. Traverse nodes at the current level: For each node in the level, dequeue it, add its value to the temporary list, and enqueue its non-null left and right children.
  5. Prepend level: Once all nodes of the current level are processed, insert the temporary list at the start of the result list. This ensures bottom-up ordering without reversing at the end.
  6. Return result: After the queue is empty, all levels are processed, and the result list contains levels from bottom to top.

Why it works: BFS guarantees that nodes are visited level by level from top to bottom. By prepending each level to the result, the last levels (leaves) naturally appear first, satisfying the bottom-up requirement. Each node is visited exactly once, ensuring correctness and efficiency.

Python Solution

from typing import List, Optional
from collections import deque

# 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

class Solution:
    def levelOrderBottom(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.insert(0, level)  # Prepend the current level
        
        return result

The Python implementation uses deque for efficient queue operations. Each level's nodes are collected in a temporary list, then inserted at the start of the result list to maintain bottom-up order. Edge cases like empty trees are handled upfront.

Go Solution

package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func levelOrderBottom(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)
            }
        }
        
        // Prepend level
        result = append([][]int{level}, result...)
    }
    
    return result
}

In Go, slices are used to simulate a queue, and prepending a slice is done by concatenation. nil checks replace Python's None checks, and slices dynamically grow to store each level.

Worked Examples

Example 1: root = [3,9,20,null,null,15,7]

Step Queue Level Result
1 [3] [] []
2 [9,20] [3] [[3]] → prepended → [[3]]
3 [15,7] [9,20] [[9,20],[3]]
4 [] [15,7] [[15,7],[9,20],[3]]

Example 2: root = [1]

Step Queue Level Result
1 [1] [1] [[1]]

Example 3: root = []

Queue is empty from the start, return [].

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each node is visited exactly once in BFS
Space O(n) Queue may store up to n/2 nodes in the last level, plus result list stores all nodes

The complexity is linear because every node is processed once, and all levels are stored in memory.

Test Cases

# Basic example trees
assert Solution().levelOrderBottom(None) == []  # empty tree
assert Solution().levelOrderBottom(TreeNode(1)) == [[1]]  # single node
assert Solution().levelOrderBottom(TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))) == [[15,7],[9,20],[3]]  # balanced tree

# Left-heavy tree
assert Solution().levelOrderBottom(TreeNode(1, TreeNode(2, TreeNode(3)))) == [[3],[2],[1]]

# Right-heavy tree
assert Solution().levelOrderBottom(TreeNode(1, None, TreeNode(2, None, TreeNode(3)))) == [[3],[2],[1]]

# Mixed tree
assert Solution().levelOrderBottom(TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3))) == [[4],[2,3],[1]]
Test Why
None Edge case for empty tree
Single node Simplest non-empty tree
Balanced tree Standard case
Left-heavy Tests handling missing right children
Right-heavy Tests handling missing left children
Mixed Checks correctness for irregular trees

Edge Cases

Empty tree: If the root is None, the queue never gets initialized with nodes. The algorithm immediately returns an empty list, preventing null reference errors.

Single node tree: Only one node exists. The BFS loop runs once, adding a list with a single element and prepending it. The result is correct, demonstrating the algorithm handles minimal input.

Highly unbalanced trees: Trees skewed to the left or right can break naive indexing approaches. Our BFS approach uses a queue, which naturally handles missing children by skipping None/nil nodes, ensuring correct bottom-up ordering without extra checks.