Binary Tree Level Order Traversal II solution and explanation
Google
9 more videos on this problem
Binary Tree Level Order Traversal ii | LeetCode 107 | C++, Java, PythonKnowledge Center · 16:38 · 10K views
Binary Tree Level Order Traversal II | LeetCode 107 | Coding Interview TutorialTerrible Whiteboard · 13:15 · 5K views
LEETCODE 107 (JAVASCRIPT) | BINARY TREE LEVEL ORDER TRAVERSAL IIAndy Gala · 8:47 · 1K views
Binary Tree Level Order Traversal II - Leetcode 107 - JavaMastering Programming · 6:37 · 904 views
Leetcode - Binary Tree Level Order Traversal II (Python)Timothy H Chang · 9:25 · 557 views
Leetcode 107 Binary Tree Level Order Traversal IIRen Zhang · 4:56 · 481 views
LeetCode 107. Binary Tree Level Order Traversal II一起来刷题! · 4:57 · 447 views
107. Binary Tree Level Order Traversal II | Leetcode MediumJOY of LIFE · 13:04 · 334 views
Leetcode 107 Binary Tree Level Order Traversal II (Java)TheAnalyticGuy · 2:01 · 325 views
LeetCode 107. Binary Tree Level Order Traversal IIEducation, the study of everything · 4:47 · 322 views
The problem
Given the root of a binary tree, return the bottom-up level order traversal of its nodes' values. (i.e., from left to right, level by level from leaf to root).
Example 1:
Input: root = [3,9,20,null,null,15,7] Output: [[15,7],[9,20],[3]]
Example 2:
Input: root = [1] Output: [[1]]
Example 3:
Input: root = [] Output: []
Constraints:
- The number of nodes in the tree is in the range
[0, 2000]. -1000 <= Node.val <= 1000
Approach overview
Problem Overview: Given the root of a binary tree, return the level order traversal of its nodes from bottom to top. Instead of listing levels starting from the root, you collect nodes level by level and return them in reverse order so the deepest level appears first.
Approach 1: Level Order Traversal with Queue and Stack (O(n) time, O(n) space)
This approach performs a standard BFS using a queue. Start by pushing the root into the queue, then repeatedly process nodes level by level. For each level, iterate through the current queue size, pop nodes, record their values, and push their children. Instead of appending each level directly to the result, push the level list onto a stack. After BFS finishes, pop from the stack to build the final bottom‑up order. Every node is visited exactly once, giving O(n) time complexity and O(n) auxiliary space for the queue, stack, and result. This is the most intuitive solution because it mirrors the normal Breadth-First Search traversal while simply reversing the level order.
Approach 2: Recursive Level Order Traversal (O(n) time, O(n) space)
This solution uses DFS recursion while tracking the current depth. Maintain a list of lists where each index corresponds to a tree level. During recursion, if the current depth equals the size of the result list, create a new level container. Insert the node value into the corresponding level, then recursively process the left and right children with depth + 1. Once traversal finishes, reverse the collected levels to produce the bottom‑up ordering. Each node is processed once, so the time complexity remains O(n), while recursion depth and storage require O(n) space in the worst case for a skewed tree. This approach works well if you prefer recursive logic over queue-based iteration.
Recommended for interviews: The BFS queue approach is typically expected because it directly matches the definition of level order traversal in a binary tree. Using a stack (or reversing the result) to adjust the order shows you understand traversal mechanics. Recursive level construction demonstrates deeper control over tree traversal but is slightly less direct for this problem.
Approach 1: 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.
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: TreeNode):
if not root:
return []
result, queue = [], deque([root])
while queue:
level_size = len(queue)
level_nodes = []
for _ in range(level_size):
node = queue.popleft()
level_nodes.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level_nodes)
return result[::-1]import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> result = new LinkedList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
List<Integer> currentLevel = new ArrayList<>();
for (int i = 0; i < levelSize; i++) {
TreeNode currentNode = queue.poll();
currentLevel.add(currentNode.val);
if (currentNode.left != null) queue.offer(currentNode.left);
if (currentNode.right != null) queue.offer(currentNode.right);
}
result.add(0, currentLevel);
}
return result;
}
}In this Python solution, we use a double-ended queue (`deque`) from the `collections` module for the traversal. A queue allows us to efficiently perform level order traversal, adding child nodes to the queue and processing them in FIFO order. After processing all levels, we invert the result list to provide a bottom-up output.
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.
Approach 2: 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.
function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
var levelOrderBottom = function(root) {
const result = [];
addToLevel(root, 0, result);
return result.reverse();
};
function addToLevel(node, level, result) {
if (!node) return;
if (result.length === level) {
result.push([]);
}
result[level].push(node.val);
addToLevel(node.left, level + 1, result);
addToLevel(node.right, level + 1, result);
}using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public IList<IList<int>> LevelOrderBottom(TreeNode root) {
List<IList<int>> result = new List<IList<int>>();
AddToLevel(root, 0, result);
result.Reverse();
return result;
}
private void AddToLevel(TreeNode node, int level, List<IList<int>> result) {
if (node == null) return;
if (result.Count == level) {
result.Add(new List<int>());
}
result[level].Add(node.val);
AddToLevel(node.left, level + 1, result);
AddToLevel(node.right, level + 1, result);
}
}In this JavaScript solution, a helper function `addToLevel` is used. It traverses the tree recursively. Each node's value is added to a sublist that corresponds to its depth, creating a level-wise list of nodes, which is then reversed to achieve the bottom-up order.
Time Complexity: O(n) where n is the number of nodes.
Space Complexity: O(n) for the recursion stack and result storage.
Approach 3: BFS
We can use the BFS (Breadth-First Search) method to solve this problem. First, enqueue the root node, then continuously perform the following operations until the queue is empty:
- Traverse all nodes in the current queue, store their values in a temporary array
t, and then enqueue their child nodes. - Store the temporary array
tin the answer array.
Finally, return the reversed answer array.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
/**
* 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) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> ans;
if (!root) {
return ans;
}
queue<TreeNode*> q{{root}};
while (!q.empty()) {
vector<int> t;
for (int n = q.size(); n; --n) {
auto node = q.front();
q.pop();
t.push_back(node->val);
if (node->left) {
q.push(node->left);
}
if (node->right) {
q.push(node->right);
}
}
ans.push_back(t);
}
reverse(ans.begin(), ans.end());
return ans;
}
};/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function levelOrderBottom(root: TreeNode | null): number[][] {
const ans: number[][] = [];
if (!root) {
return ans;
}
const q: TreeNode[] = [root];
while (q.length) {
const t: number[] = [];
const qq: TreeNode[] = [];
for (const { val, left, right } of q) {
t.push(val);
left && qq.push(left);
right && qq.push(right);
}
ans.push(t);
q.splice(0, q.length, ...qq);
}
return ans.reverse();
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func levelOrderBottom(root *TreeNode) (ans [][]int) {
if root == nil {
return
}
q := []*TreeNode{root}
for len(q) > 0 {
t := []int{}
for n := len(q); n > 0; n-- {
node := q[0]
q = q[1:]
t = append(t, node.Val)
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
}
ans = append(ans, t)
}
for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 {
ans[i], ans[j] = ans[j], ans[i]
}
return
}// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::{cell::RefCell, collections::VecDeque, rc::Rc};
impl Solution {
pub fn level_order_bottom(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
let mut ans = Vec::new();
if let Some(root_node) = root {
let mut q = VecDeque::new();
q.push_back(root_node);
while !q.is_empty() {
let mut t = Vec::new();
for _ in 0..q.len() {
if let Some(node) = q.pop_front() {
let node_ref = node.borrow();
t.push(node_ref.val);
if let Some(ref left) = node_ref.left {
q.push_back(Rc::clone(left));
}
if let Some(ref right) = node_ref.right {
q.push_back(Rc::clone(right));
}
}
}
ans.push(t);
}
}
ans.reverse();
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Level Order Traversal with Queue and Stack | Time Complexity: O(n) where n is the number of nodes, as each node is processed once. |
| Approach 2: Recursive Level Order Traversal | Time Complexity: O(n) where n is the number of nodes. |
| BFS | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Level Order Traversal with Queue and Stack | O(n) | O(n) | Standard solution for level order problems. Best when using iterative BFS. |
| Recursive Level Order Traversal | O(n) | O(n) | Useful when you prefer DFS recursion or already track levels during traversal. |
Frequently asked questions
Is Binary Tree Level Order Traversal II easy or hard?
Binary Tree Level Order Traversal II is generally classified as a Medium difficulty problem. The traversal itself is straightforward BFS, but recognizing that the result must be reversed or stacked adds a small twist compared to the standard level order traversal.
How to solve Binary Tree Level Order Traversal II in O(n)?
Use BFS with a queue to traverse the tree level by level. For each level, collect node values and store them in a list. After traversal, reverse the list of levels or use a stack to build the result in bottom-up order. Each node is processed once, giving O(n) time complexity.
Binary Tree Level Order Traversal II Python or Java solution
Python and Java implementations typically use a queue (such as collections.deque in Python or LinkedList in Java) to perform BFS. Each level is processed using the current queue size, and results are reversed or inserted at the front to produce the bottom-up order.
What is the best approach for Binary Tree Level Order Traversal II?
The most common solution uses Breadth-First Search (BFS) with a queue to process nodes level by level. Each level is stored and then reversed at the end, or pushed into a stack while traversing. This approach visits each node once and runs in O(n) time with O(n) space.
What data structure is used in Binary Tree Level Order Traversal II?
The primary data structure is a queue for Breadth-First Search traversal. A stack or list reversal is also used to produce the bottom-up ordering of levels. In recursive implementations, the call stack and a dynamic list of levels store intermediate results.
What is the time complexity of Binary Tree Level Order Traversal II?
Binary Tree Level Order Traversal II runs in O(n) time where n is the number of nodes in the tree. Every node is visited exactly once during traversal. Additional storage for levels, queue, or stack leads to O(n) space complexity.
Is Binary Tree Level Order Traversal II asked at Google, Amazon, or Meta?
Binary tree traversal problems are common in interviews at companies like Amazon, Google, and Meta. Variants of level order traversal frequently appear because they test BFS fundamentals, tree data structures, and queue usage.