The Binary Tree Level Order Traversal II problem asks you to traverse a binary tree in level order (also known as breadth-first order), but with a twist: you must return the values of the nodes from the bottom level up to the root, instead of from the root down.
Given the root node of a binary tree, you should return a list of lists, where each inner list contains the values of the nodes at that particular level, ordered from left to right. The final result should list the levels starting from the lowest (leaf) level up to the root.
Constraints:
The standard level order traversal processes nodes from the root down to the leaves, collecting nodes level by level. In this problem, however, we need the levels in reverse order: from the leaves up to the root.
A brute-force approach might be to perform a normal level order traversal and then reverse the resulting list at the end. Alternatively, one could try to traverse the tree recursively and collect nodes by their depth, but this adds complexity.
The key insight is that we can use a queue to perform a breadth-first search (BFS), collect each level's nodes, and then simply reverse the list of levels before returning. This is efficient and leverages the natural order of BFS traversal.
We solve the problem using a breadth-first search (BFS) algorithm with the following steps:
root is null (or None), return an empty list immediately.
collections.deque in Python or a LinkedList in Java) to keep track of nodes to process. Start by enqueuing the root.
This approach is efficient and clear. We use a queue for BFS because it allows us to process nodes in the correct order (left to right, level by level), and reversing the result at the end gives us the bottom-up order required.
Let's walk through an example:
Consider the following binary tree:
3
/ \
9 20
/ \
15 7
Step-by-step traversal:
3. Add [3] to the result.
9 and 20. Add [9, 20] to the result.
15 and 7. Add [15, 7] to the result.
The result after traversal is [[3], [9, 20], [15, 7]]. Reverse it to get [[15, 7], [9, 20], [3]].
Brute-force Approach: If we used recursion to collect nodes at each depth and then reversed the result, the time and space complexity would still be O(N), where N is the number of nodes, but with more overhead due to recursion stack and list operations.
Optimized BFS Approach:
O(N) — Every node is visited exactly once.
O(N) — The queue can hold up to a full level of the tree, and the result list contains all nodes.
The Binary Tree Level Order Traversal II problem is elegantly solved with a breadth-first search, collecting each level's values and then reversing the result to achieve the required bottom-up order. This approach is efficient, easy to understand, and leverages the natural properties of a queue for level order traversal. The key insight is recognizing that reversing the standard level order output is all that's needed to satisfy the problem's requirements.
from collections import deque
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):
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[::-1]
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> result;
if (!root) return result;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int levelSize = q.size();
vector<int> level;
for (int i = 0; i < levelSize; ++i) {
TreeNode* node = q.front();
q.pop();
level.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
result.push_back(level);
}
reverse(result.begin(), result.end());
return result;
}
};
import java.util.*;
public class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < levelSize; ++i) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
result.add(level);
}
Collections.reverse(result);
return result;
}
}
// Definition for a binary tree node.
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrderBottom = function(root) {
if (!root) return [];
const result = [];
const queue = [root];
while (queue.length > 0) {
const levelSize = queue.length;
const level = [];
for (let i = 0; i < levelSize; ++i) {
const node = queue.shift();
level.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(level);
}
return result.reverse();
};