MediumTreeBreadth-First SearchBinary Tree

Binary Tree Level Order Traversal II

1 approach, code in every language

Given the root of a binary tree, produce the values of its nodes grouped by depth, but ordered from the bottom level up to the top.

Concretely, the first inner list should contain the deepest (leaf) level read left to right, the next list the level above it, and so on, ending with the list that holds just the root. This is the ordinary level-order (breadth-first) grouping with the outer list reversed.

Example 1

Input: root = [3,9,20,null,null,15,7]

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

Top-down the levels are [3], [9,20], [15,7]. Reading them from the bottom up yields [[15,7],[9,20],[3]].

Example 2

Input: root = [1]

Output: [[1]]

A single node forms one level, and reversing a one-level list changes nothing.

Constraints

The number of nodes in the tree is in the range [0, 2000].
-1000 <= Node.val <= 1000

BFS by Level, Then Reverse

Run a standard breadth-first sweep that gathers each level into its own list, then reverse the collection of levels.

Loading animation…

Intuition

The bottom-up requirement is just a presentation twist on plain level-order traversal, so the core work is a normal breadth-first search. Keep a queue seeded with the root, and repeatedly process the queue one full level at a time by snapshotting its current size before draining it. Everything popped during that snapshot belongs to the same depth, and their children become the next level. Collect each level's values into a list and append it in top-down order. Once the traversal finishes, reversing the outer list (or inserting each level at the front as you go) flips the order to bottom-up.

Algorithm walkthrough

1If the root is null, return an empty list since there are no levels to report.
2Initialize a queue containing the root and an empty results list.
3While the queue is not empty, record its size; that many nodes make up the current level.
4Pop exactly that many nodes, appending each value to a fresh level list and enqueuing any non-null children for the next round.
5Append the completed level list to the results in the natural top-down order.
6After the loop ends, reverse the results list so the deepest level comes first, then return it.

Implementation

from collections import deque

class Solution:
    def levelOrderBottom(self, root: 'TreeNode') -> list[list[int]]:
        if root is None:
            return []
        result = []
        queue = deque([root])
        while queue:
            level = []
            for _ in range(len(queue)):
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(level)
        result.reverse()
        return result

Time

O(n)

Space

O(n)

Each node is enqueued and dequeued once for O(n) time. The queue and output together hold up to O(n) values; the final reverse is O(number of levels).

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Trees & BST

After the pattern

Now solve one you haven't seen.

Reading A Binary Tree Deepest Level First is our own problem on the technique behind Binary Tree Level Order Traversal II: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free