Binary tree level order traversal II

Given the root of a binary tree, return its values level by level from the bottom up: the deepest level first and the root last. Within each level, list the nodes from left to right.

Interface

Unless you agree on a different interface with the interviewer, assume:

• TreeNode has val, left and right.
• levels_bottom_up(root: TreeNode | None) -> list[list[int]] — [] for an empty tree.

Example

1 with children 2 and 3; 2 has children 4 and 5; 3 has a right child 6
levels_bottom_up(root)  ->  [[4, 5, 6], [2, 3], [1]]

3 with children 9 and 20; 20 has children 15 and 7
levels_bottom_up(root)  ->  [[15, 7], [9, 20], [3]]

levels_bottom_up(None)  ->  []

Constraints

• 0 <= number of nodes <= 10^5; the tree may be very unbalanced.

Clarifying questions

• Within a level, left to right or right to left?
• Should an empty tree give []?
• Can the tree be deep enough that recursion would overflow the stack?

What a strong answer covers

• Breadth-first search with a queue, taking the queue's size at the start of each level so every level becomes one list.
• Reverse the list of levels at the end (or insert at the front of a deque), not each level's contents.
• O(n) time and O(width) extra space; iterative, so a 10^5-deep chain is safe.
• Tests: empty tree, one node, a chain, a full tree.

Follow-ups

• Do it with depth-first search, keyed by depth.
• Print each level right to left instead.
• Return only the last node of each level (the right side view).