1. Problem Statement

Given the root of a binary tree, return the bottom-up level order traversal of its nodes’ values.
That is, traverse the tree level by level from left to right, but return the levels from bottom to top.

Example 1:
Input:

    3
   / \
  9  20
    /  \
   15   7

Output: [[15,7],[9,20],[3]]

Example 2:
Input: root = [1]
Output: [[1]]

Example 3:
Input: root = []
Output: []

---

2. Key Insight

This problem is a variation of Level Order Traversal (BFS).
The difference is that we must return the result in reverse order (from bottom to top).

To achieve this:

1. Perform a standard BFS traversal using a queue.
2. For each level, collect all node values into a list.
3. After BFS completes, reverse the list of levels before returning.

---

3. Approach 1: BFS (Queue) + Reverse

Steps:

1. If the tree is empty, return an empty list.
2. Use a queue to perform level order traversal.
3. For each level:
   • Determine the number of nodes (size = queue.size()).
   • Extract all nodes at this level.
   • Add their values to a temporary list.
   • Enqueue their left and right children (if any).
4. After BFS completes, reverse the list of levels.

---

4. Java Implementation

import java.util.*;

public class BinaryTreeLevelOrderTraversalII {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    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 size = queue.size();
            List<Integer> level = new ArrayList<>();

            for (int i = 0; i < size; 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;
    }

    public static void main(String[] args) {
        BinaryTreeLevelOrderTraversalII.TreeNode root = new BinaryTreeLevelOrderTraversalII.TreeNode(3);
        root.left = new BinaryTreeLevelOrderTraversalII.TreeNode(9);
        root.right = new BinaryTreeLevelOrderTraversalII.TreeNode(20);
        root.right.left = new BinaryTreeLevelOrderTraversalII.TreeNode(15);
        root.right.right = new BinaryTreeLevelOrderTraversalII.TreeNode(7);

        BinaryTreeLevelOrderTraversalII obj = new BinaryTreeLevelOrderTraversalII();
        System.out.println(obj.levelOrderBottom(root)); // [[15,7],[9,20],[3]]
    }
}

---

5. Complexity Analysis

Operation	Complexity	Explanation
Time	O(n)	Each node is processed exactly once
Space	O(n)	Queue and result lists hold at most n elements

---

6. Approach 2: DFS (Recursive Traversal)

Instead of using a queue, we can also use recursion to traverse levels top-down, and then reverse at the end.

Idea:

• Perform DFS and store values level by level using recursion.
• Use a list where the index corresponds to the level depth.
• Reverse the final list before returning.

Code:

import java.util.*;

public class BinaryTreeLevelOrderTraversalII_DFS {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> levels = new ArrayList<>();
        dfs(root, 0, levels);
        Collections.reverse(levels);
        return levels;
    }

    private void dfs(TreeNode node, int level, List<List<Integer>> levels) {
        if (node == null) return;
        if (levels.size() == level)
            levels.add(new ArrayList<>());

        levels.get(level).add(node.val);
        dfs(node.left, level + 1, levels);
        dfs(node.right, level + 1, levels);
    }
}

Complexity:

• Time: O(n)
• Space: O(n) (for recursion stack and list storage)

---

7. Dry Run

Let’s dry run BFS approach on the input:

    3
   / \
  9  20
    /  \
   15   7

Initial State:

• queue = [3]
• result = []

Step 1: Level 1

• size = 1
• Pop 3, add to level → level = [3]
• Enqueue 9, 20
• After loop → result = [[3]]
• queue = [9, 20]

Step 2: Level 2

• size = 2
• Pop 9 → add to level
• Pop 20 → add to level, enqueue its children 15, 7
• level = [9, 20]
• result = [[3], [9, 20]]
• queue = [15, 7]

Step 3: Level 3

• size = 2
• Pop 15, then 7
• level = [15, 7]
• result = [[3], [9, 20], [15, 7]]
• queue = [] (empty)

Final Step: Reverse

• result = [[15, 7], [9, 20], [3]]

Output: [[15,7],[9,20],[3]]

---

8. Key Takeaways

• Use BFS with a queue for clarity and level grouping.
• Use DFS if you prefer recursion-based level building.
• Always reverse at the end to get bottom-up order.
• Both approaches have O(n) time complexity.