Binary Tree Level Order Traversal II

Med

#0107Time: O(N)Space: O(N)3 companies

Algorithms

Breadth-First Search

Data structures

Tree Binary Tree

Companies

Google Meta Revolut

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach uses a recursive Depth-First Search (DFS) to traverse the tree. It keeps track of the level of each node to group them correctly. The levels are gathered in a top-down order, and the final list of levels is reversed to achieve the required bottom-up order.

Algorithm

Initialize an empty list of lists, result.
If the root is null, return the empty result.
Create a recursive helper function, dfs(node, level, result).
Call the helper function with the root, level 0, and the result list.
Inside the helper function:
- Base case: if the node is null, return.
- If level is equal to result.size(), it's the first time we're visiting this level. Add a new empty list to result.
- Add the node's value to the list at index level: result.get(level).add(node.val).
- Recursively call for the left child: dfs(node.left, level + 1, result).
- Recursively call for the right child: dfs(node.right, level + 1, result).
After the initial DFS call returns, the result list contains the levels in top-down order.
Reverse the result list using Collections.reverse().
Return the reversed list.

Walkthrough

We can perform a pre-order traversal on the tree while keeping track of the current level. We use a list of lists, result, to store the nodes for each level. The level variable acts as an index into this result list. When we visit a node at a level for the first time, we add a new list to result. Then, we add the node's value to the list corresponding to its level. After the traversal is complete, result will hold the levels from top to bottom. The final step is to reverse this result list to get the bottom-up order.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public List<List<Integer>> levelOrderBottom(TreeNode root) {18        List<List<Integer>> result = new ArrayList<>();19        if (root == null) {20            return result;21        }22        dfs(root, 0, result);23        Collections.reverse(result);24        return result;25    }26 27    private void dfs(TreeNode node, int level, List<List<Integer>> result) {28        if (node == null) {29            return;30        }31        // If we are visiting a new level, add a new list for it.32        if (level >= result.size()) {33            result.add(new ArrayList<>());34        }35        // Add the node's value to the list for its level.36        result.get(level).add(node.val);37        38        // Recurse for children.39        dfs(node.left, level + 1, result);40        dfs(node.right, level + 1, result);41    }42}

Complexity

Time

O(N)

Space

O(N)

Trade-offs

Pros

Conceptually simple if one is familiar with DFS and recursion.
Follows a standard tree traversal pattern.

Cons

Requires an extra step to reverse the final list.
The recursive approach can lead to a StackOverflowError for very deep or skewed trees.
The space complexity for the recursion stack is O(H), where H is the tree height, which can be O(N) for a skewed tree.

This approach performs a standard top-down level order traversal using a queue (which is a Breadth-First Search). The nodes are processed level by level, and each level is stored in a list. After all levels are collected in top-down order, the entire list of levels is reversed.

Algorithm

Initialize an empty ArrayList of lists, result.
If the root is null, return the empty result.
Initialize a Queue and add the root node to it.
While the queue is not empty:
- Get the number of nodes at the current level (levelSize = queue.size()).
- Create a new list currentLevel to store node values for this level.
- Loop levelSize times:
  - Dequeue a node.
  - Add its value to currentLevel.
  - If the node has a non-null left child, enqueue it.
  - If the node has a non-null right child, enqueue it.
- Add currentLevel to the result list.
After the loop, reverse the result list using Collections.reverse().
Return the reversed list.

Walkthrough

This is a straightforward two-pass approach. The first pass consists of a standard Breadth-First Search (BFS) to get the level order traversal from top to bottom. We use a queue to keep track of nodes to visit. In each iteration of the main loop, we process all nodes at the current level. The values of these nodes are stored in a temporary list, which is then added to our main result list. After the BFS is complete, the result list contains all levels in order from root to leaves. The second pass is to simply reverse this list to meet the problem's requirement of a bottom-up traversal.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public List<List<Integer>> levelOrderBottom(TreeNode root) {18        List<List<Integer>> result = new ArrayList<>();19        if (root == null) {20            return result;21        }22        Queue<TreeNode> queue = new LinkedList<>();23        queue.offer(root);24 25        while (!queue.isEmpty()) {26            int levelSize = queue.size();27            List<Integer> currentLevel = new ArrayList<>();28            for (int i = 0; i < levelSize; i++) {29                TreeNode node = queue.poll();30                currentLevel.add(node.val);31                if (node.left != null) {32                    queue.offer(node.left);33                }34                if (node.right != null) {35                    queue.offer(node.right);36                }37            }38            result.add(currentLevel);39        }40 41        Collections.reverse(result);42        return result;43    }44}

Complexity

Time

O(N)

Space

O(N)

Trade-offs

Pros

The iterative BFS approach avoids recursion, preventing potential StackOverflowError on very deep trees.
It's a very common and well-understood pattern for tree problems.
Generally more space-efficient on the auxiliary data structure (queue) for skewed trees compared to DFS's recursion stack.

Cons

Requires an extra pass (or operation) to reverse the list of levels after the traversal is complete.

This is an optimized version of the BFS approach. It performs a standard level order traversal but cleverly builds the result list in the desired bottom-up order from the start. Instead of appending each level's list to the end and reversing later, it prepends each level's list to the front of the result list.

Algorithm

Initialize an empty LinkedList of lists, result. Using a LinkedList is crucial for efficient prepending.
If the root is null, return the empty result.
Initialize a Queue and add the root node to it.
While the queue is not empty:
- Get the number of nodes at the current level (levelSize = queue.size()).
- Create a new list currentLevel to store node values for this level.
- Loop levelSize times:
  - Dequeue a node.
  - Add its value to currentLevel.
  - If the node has a non-null left child, enqueue it.
  - If the node has a non-null right child, enqueue it.
- Add currentLevel to the beginning of the result list using result.add(0, currentLevel).
After the loop, the result list is already in bottom-up order. Return it.

Walkthrough

This approach refines the standard BFS traversal by eliminating the final reversal step. We still process the tree level by level from top to bottom using a queue. However, when we finish processing a level, we add its corresponding list of values to the beginning of our result list. To make this prepending operation efficient (O(1)), the result list should be implemented as a LinkedList. By always adding new levels to the front, the list naturally gets built in reverse order, resulting in the desired bottom-up traversal directly.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public List<List<Integer>> levelOrderBottom(TreeNode root) {18        // Use LinkedList for efficient prepending (addFirst or add(0, ...))19        List<List<Integer>> result = new LinkedList<>();20        if (root == null) {21            return result;22        }23        Queue<TreeNode> queue = new LinkedList<>();24        queue.offer(root);25 26        while (!queue.isEmpty()) {27            int levelSize = queue.size();28            List<Integer> currentLevel = new ArrayList<>();29            for (int i = 0; i < levelSize; i++) {30                TreeNode node = queue.poll();31                currentLevel.add(node.val);32                if (node.left != null) {33                    queue.offer(node.left);34                }35                if (node.right != null) {36                    queue.offer(node.right);37                }38            }39            // Add the level at the beginning of the list40            result.add(0, currentLevel);41        }42        return result;43    }44}

Complexity

Time

O(N)

Space

O(N)

Trade-offs

Pros

Builds the result in the correct bottom-up order directly, avoiding a final reversal step.
It's an elegant single-pass solution (over the nodes).
Iterative, so no risk of stack overflow.

Cons

Using a LinkedList for the result list might have slightly higher memory overhead and worse cache performance compared to an ArrayList, though the asymptotic complexity remains the same.

Solutions

Solution

1/** * Definition for a binary tree node. * public 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; * } * } */ class Solution { public List < List < Integer >> levelOrderBottom ( TreeNode root ) { LinkedList < List < Integer >> ans = new LinkedList <>(); if ( root == null ) { return ans ; } Deque < TreeNode > q = new LinkedList <>(); q . offerLast ( root ); while (! q . isEmpty ()) { List < Integer > t = new ArrayList <>(); for ( int i = q . size (); i > 0 ; -- i ) { TreeNode node = q . pollFirst (); t . add ( node . val ); if ( node . left != null ) { q . offerLast ( node . left ); } if ( node . right != null ) { q . offerLast ( node . right ); } } ans . addFirst ( t ); } return ans ; } }

1/** * 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 =2  function (root) {3    const ans = [];4    if (!root) return ans;5    const q = [root];6    while (q.length) {7      const t = [];8      for (let i = q.length; i > 0; --i) {9        const node = q.shift();10        t.push(node.val);11        if (node.left) q.push(node.left);12        if (node.right) q.push(node.right);13      }14      ans.unshift(t);15    }16    return ans;17  };

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) {} * }; */ 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 i = q . size (); i ; -- i ) { auto node = q . front (); q . pop (); t . emplace_back ( node -> val ); if ( node -> left ) q . push ( node -> left ); if ( node -> right ) q . push ( node -> right ); } ans . emplace_back ( t ); } reverse ( ans . begin (), ans . end ()); return ans ; } };

1# 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 ]]: ans = [] if root is None : return ans q = deque ([ root ]) while q : t = [] for _ in range ( len ( q )): node = q . popleft () t . append ( node . val ) if node . left : q . append ( node . left ) if node . right : q . append ( node . right ) ans . append ( t ) return ans [:: - 1 ]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1/** * Definition for a binary tree node. * public 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; * } * } */ class Solution { public List < List < Integer >> levelOrderBottom ( TreeNode root ) { LinkedList < List < Integer >> ans = new LinkedList <>(); if ( root == null ) { return ans ; } Deque < TreeNode > q = new LinkedList <>(); q . offerLast ( root ); while (! q . isEmpty ()) { List < Integer > t = new ArrayList <>(); for ( int i = q . size (); i > 0 ; -- i ) { TreeNode node = q . pollFirst (); t . add ( node . val ); if ( node . left != null ) { q . offerLast ( node . left ); } if ( node . right != null ) { q . offerLast ( node . right ); } } ans . addFirst ( t ); } return ans ; } }

1/** * 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 =2  function (root) {3    const ans = [];4    if (!root) return ans;5    const q = [root];6    while (q.length) {7      const t = [];8      for (let i = q.length; i > 0; --i) {9        const node = q.shift();10        t.push(node.val);11        if (node.left) q.push(node.left);12        if (node.right) q.push(node.right);13      }14      ans.unshift(t);15    }16    return ans;17  };

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) {} * }; */ 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 i = q . size (); i ; -- i ) { auto node = q . front (); q . pop (); t . emplace_back ( node -> val ); if ( node -> left ) q . push ( node -> left ); if ( node -> right ) q . push ( node -> right ); } ans . emplace_back ( t ); } reverse ( ans . begin (), ans . end ()); return ans ; } };

1# 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 ]]: ans = [] if root is None : return ans q = deque ([ root ]) while q : t = [] for _ in range ( len ( q )): node = q . popleft () t . append ( node . val ) if node . left : q . append ( node . left ) if node . right : q . append ( node . right ) ans . append ( t ) return ans [:: - 1 ]

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.