Reverse Level Order Traversal (Bottom-up Level Order)

• Reverse level order – return node values level by level from the bottom level up to the root.
• BFS with prepend – process the tree top-down with a queue, but insert each completed level at the front of the result.
• LinkedList.addFirst – O(1) prepend keeps the whole operation linear.
• Alternative – collect top-down into an ArrayList and reverse once at the end.
• Complexity – O(n) time, O(n) space.

What is the problem?

Given the root of a binary tree, return its node values level by level but from the bottom level up to the root, left to right within each level. For example, a tree with levels [1], [2,3], [4,5,6] returns [[4,5,6], [2,3], [1]].

At the National Bank of India, the audit report must show the hierarchy from clerks up to the branch manager.

How does standard BFS level-order work?

Use a FIFO queue. At each level, record the queue size, process exactly that many nodes, enqueue their children, and collect the level's values.

// Standard top-down level order
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); // top-down: append
}

How do you make it bottom-up?

Change one line: instead of appending each level, prepend it.

package com.bank.analytics;

import java.util.*;

public class ReverseLevelOrder {
    public static List<List<Integer>> reverseLevelOrder(TreeNode root) {
        LinkedList<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> 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.addFirst(level); // bottom-up: prepend
        }
        return result;
    }

    public static void main(String[] args) {
        // Tree:     1
        //          / \
        //         2   3
        //        / \
        //       4   5
        TreeNode root = new TreeNode(1,
            new TreeNode(2, new TreeNode(4), new TreeNode(5)),
            new TreeNode(3));
        System.out.println(reverseLevelOrder(root));
    }
}

[[4, 5], [2, 3], [1]]

Why use LinkedList instead of ArrayList for prepending?

LinkedList.addFirst() is O(1) because it adjusts head pointers. ArrayList.add(0, x) is O(n) because it shifts all existing elements one position to the right. Over all levels, this turns a linear algorithm into a quadratic one.

// Wrong: O(n) per insert -> O(n^2) total
ArrayList<List<Integer>> result = new ArrayList<>();
result.add(0, level); // shifts all existing levels

// Correct: O(1) per insert -> O(n) total
LinkedList<List<Integer>> result = new LinkedList<>();
result.addFirst(level); // no shifting

What is the alternative approach?

Collect levels top-down into an ArrayList, then reverse the list once at the end.

List<List<Integer>> result = new ArrayList<>();
// ... standard BFS adding levels to result ...
Collections.reverse(result); // O(number of levels)

Both approaches are O(n) overall. The prepend approach avoids the explicit reverse call.

What is the time and space complexity?

| Aspect | Complexity |
|---|---|
| Time | O(n), visit each node once |
| Space | O(n) for the queue + O(n) for the result |

What are common mistakes?

Using ArrayList.add(0, level) instead of LinkedList.addFirst(level), which silently degrades to O(n^2).

Forgetting the null check for the root, which causes a NullPointerException when the tree is empty.

What are the edge cases?

• Empty tree (null root): return an empty list.
• Single node: return [[value]].
• Skewed tree (all left children): each level has one node; result is reversed single-element levels.

What should a senior engineer know?

This problem tests whether you understand that the traversal order and the accumulation order are independent. BFS always processes top-down, but how you store the results determines the output order.

The same pattern applies to zigzag level order, where even levels go left-to-right and odd levels go right-to-left. The BFS is the same; only the per-level collection order changes.

What are common interview follow-up questions?

• Zigzag level order? (Alternate the direction within each level using a deque or reverse.)
• Average of levels? (Compute sum and count per level.)
• Right-side view of the tree? (Take the last node of each level.)