Binary Tree Level Order Traversal II — Problem & Solution
Binary Tree Level Order Traversal II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Binary Tree Level Order Traversal II is a medium coding problem on breadth-first search and trees, asked in Amazon and Microsoft interviews.
- Difficulty: Medium
- Topics: Breadth-First Search, Trees
- Asked at: Amazon, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the root of a binary tree, return its node values level by level from the bottom up: the deepest level first and the root's level last, each level read from left to right.
Example 1
Input: root = [3,9,20,null,null,15,7]
Output: [[15,7],[9,20],[3]]
Explanation: The deepest level (15, 7) comes first and the root's level last; each level still reads left to right.
Example 2
Input: root = [1]
Output: [[1]]
Explanation: A single node is a single level.
Example 3
Input: root = []
Output: []
Explanation: An empty tree has no levels.
Constraints
0 <= number of nodes <= 2000-1000 <= Node.val <= 1000
Hints for Binary Tree Level Order Traversal II
Hint 1
The levels themselves are the ordinary top-down level-order ones — only their order in the answer changes.
Hint 2
Collect the levels top-down with a breadth-first queue, one list per level.
Hint 3
Reverse the list of levels at the end (not the values inside each level).
How to solve Binary Tree Level Order Traversal II
Bottom-up order is top-down level order with the list of levels reversed, so do a normal breadth-first traversal and reverse once at the end.
Approach
- If the tree is empty, return an empty list.
- Process the tree level by level with a queue, children added left before right, appending one list of values per level.
- Reverse the order of the lists and return them.
Why it works
The breadth-first traversal produces each level's values left to right, in order of depth; reversing the outer list puts the deepest level first without touching the left-to-right order inside a level.
Complexity
- Time —
O(n) - Space —
O(w) for the queue, w the largest number of nodes on one level (plus the output)
Pitfalls
- Reverse the list of levels, not the values within each level.
- Inserting every level at the front of an array list costs O(L^2) moves; collect then reverse once.
Reference solution
Python
from typing import List, Optional
def levelOrderBottom(root: Optional[TreeNode]) -> List[List[int]]:
out = []
level = [root] if root else []
while level:
out.append([node.val for node in level])
nxt = []
for node in level:
if node.left:
nxt.append(node.left)
if node.right:
nxt.append(node.right)
level = nxt
out.reverse()
return outJava
public static int[][] levelOrderBottom(TreeNode root) {
List<int[]> out = new ArrayList<>();
Deque<TreeNode> queue = new ArrayDeque<>();
if (root != null) queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
int[] row = new int[size];
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
row[i] = node.val;
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
out.add(row);
}
Collections.reverse(out);
return out.toArray(new int[0][]);
}C++
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> out;
queue<TreeNode*> q;
if (root) q.push(root);
while (!q.empty()) {
int size = (int) q.size();
vector<int> row;
for (int i = 0; i < size; i++) {
TreeNode* node = q.front();
q.pop();
row.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
out.push_back(row);
}
reverse(out.begin(), out.end());
return out;
}JavaScript
var levelOrderBottom = function(root) {
var out = [];
if (root === null) return out;
var queue = [root], head = 0;
while (head < queue.length) {
var end = queue.length, row = [];
while (head < end) {
var node = queue[head++];
row.push(node.val);
if (node.left !== null) queue.push(node.left);
if (node.right !== null) queue.push(node.right);
}
out.push(row);
}
return out.reverse();
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 156 breadth-first search problems · the whole catalogue
Learn the technique: Breadth-First Search (BFS) · Binary Trees and Tree Traversals