Binary Tree Level Order Traversal II
Medium · Trees · Tree · Breadth-First Search · Binary Tree
Problem
Given the root of a binary tree, return its level order traversal from the bottom up: the deepest level first and the root’s level last, with the values of each level listed left to right.
Examples
Input: root = [5,1,8,None,3,7] Output: [[3,7],[1,8],[5]]
The levels from the top are [5], [1,8] and [3,7]; listed from the bottom they are reversed.
Input: root = [] Output: []
No nodes, no levels.
Input: root = [3,9,20,None,None,15,7] Output: [[15,7],[9,20],[3]]
Top-down the levels are [3], [9,20] and [15,7].
Constraints
- 0 <= number of nodes <= 2000
- -1000 <= Node.val <= 1000
Approaches
- Baseline: one pass per depth — time O(n · h), space O(h)
Follow-up
Could you build the answer without reversing at the end? Find the height first and fill the levels into a list of that size from the back, or recurse and place each value at index height - 1 - depth. See the use cases for per-level sums from the bottom up, and for grouping nodes by their height instead of their depth.
Related problems
Start free on Cariara · Coding problems · System design studio
