# Binary Tree Level Order Traversal II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/binary-tree-level-order-traversal-ii)
Canonical: https://scaleengineer.com/dsa/problems/binary-tree-level-order-traversal-ii
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Tree, Binary Tree
**Companies:** [Google](https://scaleengineer.com/companies/google), [Meta](https://scaleengineer.com/companies/meta), [Revolut](https://scaleengineer.com/companies/revolut)
---
## 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:**

![](https://assets.glich.co/dsa/binary-tree-level-order-traversal-ii/image0.jpg) 

**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
## Depth-First Search (DFS) with Reversal
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.
**Time:** O(N) · **Space:** O(N)
**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.
### Explanation
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.

```java
/**
 * 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) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        dfs(root, 0, result);
        Collections.reverse(result);
        return result;
    }

    private void dfs(TreeNode node, int level, List<List<Integer>> result) {
        if (node == null) {
            return;
        }
        // If we are visiting a new level, add a new list for it.
        if (level >= result.size()) {
            result.add(new ArrayList<>());
        }
        // Add the node's value to the list for its level.
        result.get(level).add(node.val);
        
        // Recurse for children.
        dfs(node.left, level + 1, result);
        dfs(node.right, level + 1, result);
    }
}
```
### 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.

## Breadth-First Search (BFS) with Reversal
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.
**Time:** O(N) · **Space:** O(N)
**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.
### Explanation
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.

```java
/**
 * 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) {
        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> currentLevel = new ArrayList<>();
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                currentLevel.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            result.add(currentLevel);
        }

        Collections.reverse(result);
        return result;
    }
}
```
### 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.

## Breadth-First Search (BFS) with Prepending
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.
**Time:** O(N) · **Space:** O(N)
**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.
### Explanation
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.

```java
/**
 * 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) {
        // Use LinkedList for efficient prepending (addFirst or add(0, ...))
        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 node = queue.poll();
                currentLevel.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            // Add the level at the beginning of the list
            result.add(0, currentLevel);
        }
        return result;
    }
}
```
### 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.

# Solutions
### Java

```java
/** * 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 ; } }
```

### JavaScript

```javascript
/** * 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) {
    const ans = [];
    if (!root) return ans;
    const q = [root];
    while (q.length) {
      const t = [];
      for (let i = q.length; i > 0; --i) {
        const node = q.shift();
        t.push(node.val);
        if (node.left) q.push(node.left);
        if (node.right) q.push(node.right);
      }
      ans.unshift(t);
    }
    return ans;
  };

```

### CPP

```cpp
/** * 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 ; } };
```

### Python

```python
# 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 ]
```