LeetCode 107: Binary Tree Level Order Traversal II

Problem Restatement

We are given the root of a binary tree.

We need to return the node values level by level, but from bottom to top. Inside each level, values must still be ordered from left to right.

The official problem asks for the bottom-up level order traversal of the binary tree’s node values, from leaf level to root level.

For this tree:

        3
      /   \
     9     20
          /  \
         15   7

Normal level order traversal is:

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

Bottom-up level order traversal is:

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

Input and Output

LeetCode gives the TreeNode class:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

The function shape is:

class Solution:
    def levelOrderBottom(self, root: Optional[TreeNode]) -> list[list[int]]:
        ...

Examples

Consider this tree:

        3
      /   \
     9     20
          /  \
         15   7

Level 0 contains:

[3]

Level 1 contains:

[9, 20]

Level 2 contains:

[15, 7]

Normal top-down order is:

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

The problem wants bottom-up order, so we reverse the list of levels:

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

For a single-node tree:

1

The answer is:

[[1]]

For an empty tree:

root = None

The answer is:

[]

First Thought: Use Normal Level Order Traversal

The problem still asks for nodes grouped by level.

That is exactly what breadth-first search gives us.

The only difference from LeetCode 102 is the final order of the levels.

So we can:

1. Run normal BFS from top to bottom.
2. Store each level as a list.
3. Reverse the final answer.

This keeps the traversal simple and makes the bottom-up part explicit.

Key Insight

We should preserve left-to-right order inside each level.

That means during BFS, we still enqueue children in this order:

left child first
right child second

This gives each level in the correct left-to-right order.

After all levels are collected, we reverse only the outer list:

ans.reverse()

We do not reverse each inner level.

For example:

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

becomes:

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

The level [15, 7] remains left to right.

Algorithm

If root is None, return [].

Otherwise:

1. Create a queue containing root.
2. Create an empty answer list.
3. While the queue is not empty:
   1. Create an empty list for the current level.
   2. Read the current queue size.
   3. Process exactly that many nodes.
   4. Append each node value to the current level list.
   5. Add the left child if it exists.
   6. Add the right child if it exists.
   7. Append the current level list to the answer.
4. Reverse the answer list.
5. Return the answer.

Correctness

The queue starts with the root, so the first processed level is the root level.

At the start of each outer loop, the queue contains exactly the nodes of one level in left-to-right order. We record the queue size before processing that level, so newly added children are not mixed into the current level.

For every processed node, the algorithm adds the left child before the right child. Therefore, the next level is also arranged from left to right in the queue.

Thus, before the final reversal, ans contains all levels from root to leaves, with left-to-right order inside each level.

The problem asks for the same levels from leaves to root. Reversing the outer list changes only the order of levels. It does not change the order of values inside each level.

Therefore, the returned list is exactly the required bottom-up level order traversal.

Complexity

Here, n is the number of nodes in the tree.

The final reversal costs O(L), where L is the number of levels. Since L <= n, the total time remains O(n).

Implementation

from collections import deque
from typing import Optional

# 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]]:
        if root is None:
            return []

        ans = []
        q = deque([root])

        while q:
            level = []

            for _ in range(len(q)):
                node = q.popleft()
                level.append(node.val)

                if node.left is not None:
                    q.append(node.left)

                if node.right is not None:
                    q.append(node.right)

            ans.append(level)

        ans.reverse()
        return ans

Code Explanation

Handle the empty tree first:

if root is None:
    return []

Create the answer list and queue:

ans = []
q = deque([root])

The queue lets us process nodes in breadth-first order.

The outer loop processes one level at a time:

while q:

For each level, start a new list:

level = []

This loop runs exactly once for every node in the current level:

for _ in range(len(q)):

Remove the next node and store its value:

node = q.popleft()
level.append(node.val)

Add children for the next level:

if node.left is not None:
    q.append(node.left)

if node.right is not None:
    q.append(node.right)

After the current level is complete, store it:

ans.append(level)

Finally, reverse the level order:

ans.reverse()
return ans

Testing

from collections import deque
from typing import Optional

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]]:
        if root is None:
            return []

        ans = []
        q = deque([root])

        while q:
            level = []

            for _ in range(len(q)):
                node = q.popleft()
                level.append(node.val)

                if node.left is not None:
                    q.append(node.left)

                if node.right is not None:
                    q.append(node.right)

            ans.append(level)

        ans.reverse()
        return ans

def run_tests():
    s = Solution()

    root1 = TreeNode(
        3,
        TreeNode(9),
        TreeNode(20, TreeNode(15), TreeNode(7)),
    )
    assert s.levelOrderBottom(root1) == [[15, 7], [9, 20], [3]]

    root2 = TreeNode(1)
    assert s.levelOrderBottom(root2) == [[1]]

    root3 = None
    assert s.levelOrderBottom(root3) == []

    root4 = TreeNode(
        1,
        TreeNode(2, TreeNode(4), TreeNode(5)),
        TreeNode(3, TreeNode(6), TreeNode(7)),
    )
    assert s.levelOrderBottom(root4) == [[4, 5, 6, 7], [2, 3], [1]]

    root5 = TreeNode(
        1,
        TreeNode(2, TreeNode(3, TreeNode(4))),
        None,
    )
    assert s.levelOrderBottom(root5) == [[4], [3], [2], [1]]

    print("all tests passed")

run_tests()

Test meaning: