List the Levels From the Bottom Up

Easy20–25 min

Topics

Binary TreeBFSQueueLevel Order

Companies

AmazonMicrosoftBloombergApple

You are given the root of a binary tree. Group the node values by level and return the groups starting from the deepest level and ending with the root's level; inside each group, keep the values in left-to-right order. For an empty tree return an empty list.

You can walk the tree repeatedly, once per level from the bottom, or collect the levels top-down with a queue in one pass and simply reverse the order of the rows.

Test Case 1:

Input:root = [17, 8, 25, 4, 12, null, 30, 2]

Output:[[2], [4, 12, 30], [8, 25], [17]]

Explanation:The levels top-down are [17], [8, 25], [4, 12, 30], [2]. The answer lists them in the opposite order: the deepest level (just node 2) first and the root last, while each level is still read left to right.

Test Case 2:

Input:root = [6, null, 9]

Output:[[9], [6]]

Explanation:Two levels, deepest first.

Test Case 3:

Input:root = []

Output:[]

Explanation:No levels.

Constraints

◆0 ≤ number of nodes ≤ 100
◆−100 ≤ node.val ≤ 100
◆The tree is given as its root node (null for an empty tree); each node has a val, a left child and a right child
◆Return one list per level, but starting with the DEEPEST level and ending with the root level. Inside each level, list the values from left to right. An empty tree gives an empty list

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Walk the Tree Once per Level, Deepest First

Brute

Find the height h of the tree, then produce the levels from depth h − 1 down to 0. For each depth, walk the whole tree again with a helper that counts down the remaining levels to descend (left child first, then right child); the nodes it finds at count 0 are that level's values, already in left-to-right order. Since the depths are visited from the bottom, the rows come out deepest-first with no reversing. But each of the h passes re-walks up to n nodes: O(n · h) time (O(n²) for a tall thin tree).

TimeO(n · h)

SpaceO(n)

Java

Try it out

class Solution {
    public List<List<Integer>> bottomUpLevels(TreeNode root) {
        List<List<Integer>> levels = new ArrayList<>();
        int h = height(root);
        for (int depth = h - 1; depth >= 0; depth--) {
            List<Integer> row = new ArrayList<>();
            collect(root, depth, row);
            levels.add(row);
        }
        return levels;
    }

    private int height(TreeNode node) {
        if (node == null) return 0;
        return 1 + Math.max(height(node.left), height(node.right));
    }

    private void collect(TreeNode node, int depth, List<Integer> row) {
        if (node == null) return;
        if (depth == 0) {
            row.add(node.val);
            return;
        }
        collect(node.left, depth - 1, row);
        collect(node.right, depth - 1, row);
    }
}

Optimal — Queue by Levels, Then Reverse the Rows

Optimal

First do the ordinary top-down level traversal with a queue: at each round the queue size is the number of nodes on the level, so take that many nodes, record their values in a row, and queue their children. Append each finished row to the answer. The rows are then in root-first order, so reversing the list of rows (a level count of at most h — cheap) yields the deepest-first order. Each node is queued and taken once: O(n) time; the answer itself needs O(n) space, and the queue holds at most one or two levels.

TimeO(n)