#107 Binary Tree Level Order Traversal II - Solution

In #107 Binary Tree Level Order Traversal II, the goal is to return the level order traversal of a binary tree from bottom to top. This means the last level of the tree should appear first in the result, and the root level should appear last.

The most common strategy is to use Breadth-First Search (BFS) with a queue. Process the tree level by level, collect node values for each level, and store them in a result list. Since BFS naturally visits nodes from top to bottom, you can either reverse the result at the end or insert each level at the beginning of the result list to maintain bottom-up order.

An alternative method uses Depth-First Search (DFS) while tracking the depth of each node. Values are grouped by depth and later reordered to produce the bottom-up traversal.

Both approaches visit each node exactly once, giving a time complexity of O(n), where n is the number of nodes. Additional space is required for storing traversal results and recursion/queue structures.

Approach	Time Complexity	Space Complexity
BFS with Queue	O(n)	O(n)
DFS with Depth Tracking	O(n)	O(n)

Solutions (4)

Approach 1: Level Order Traversal with Queue and Stack

This approach utilizes a queue to perform a standard level order traversal but stores each level of nodes in a separate list. After the traversal, the entire list of lists is reversed to provide the bottom-up level order.

Time Complexity: O(n) where n is the number of nodes, as each node is processed once.
Space Complexity: O(n) for storing the queue and the result.

Python Java

1import java.util.*;
2
3class TreeNode {
4    int val;
5    TreeNode left;
6    TreeNode right;
7    TreeNode(int x) { val = x; }
8}
9
10class Solution {
11    public List<List<Integer>> levelOrderBottom(TreeNode root) {
12        List<List<Integer>> result = new LinkedList<>();
13        if (root == null) return result;
14
15        Queue<TreeNode> queue = new LinkedList<>();
16        queue.offer(root);
17        while (!queue.isEmpty()) {
18            int levelSize = queue.size();
19            List<Integer> currentLevel = new ArrayList<>();
20            for (int i = 0; i < levelSize; i++) {
21                TreeNode currentNode = queue.poll();
22                currentLevel.add(currentNode.val);
23                if (currentNode.left != null) queue.offer(currentNode.left);
24                if (currentNode.right != null) queue.offer(currentNode.right);
25            }
26            result.add(0, currentLevel);
27        }
28
29        return result;
30    }
31}

Explanation

The Java solution uses a `Queue` for level order traversal similar to BFS. Instead of reversing the final result, each level is added at the beginning of the results list, achieving a bottom-up order directly.

Approach 2: Recursive Level Order Traversal

This recursive approach traverses the tree, keeping track of the depth of each node. Nodes are added to sublists based on their depth, and the list of lists is reversed at the end to provide bottom-up level order.

Time Complexity: O(n) where n is the number of nodes.
Space Complexity: O(n) for the recursion stack and result storage.

JavaScript C#