List a Binary Tree's Levels from the Deepest Level Up to the Root
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Overview: Google new-grad onsite coding problem: given a binary tree in level-order form, return its node values grouped by depth, from the deepest level up to the root and left to right within each level. Tests breadth-first traversal and handling of unbalanced and empty trees.
Constraints
- 0 <= number of nodes <= 10^4
- -10^4 <= node value <= 10^4; values may repeat.
- The tree is not necessarily balanced; its height can be as large as the number of nodes.
- tree is a level-order listing: None marks a missing child, a missing node has no child slots, trailing None entries may be omitted, and tree[0] is never None when tree is non-empty.
Examples
Input: ([3, 9, 20, None, None, 15, 7],)
Expected Output: [[15, 7], [9, 20], [3]]
Explanation: Source Example 1: 9 is a leaf whose two None slots are consumed, 15 and 7 are children of 20; levels are listed deepest first and left to right within each level.
Input: ([1, 2, 3, 4, None, None, 5],)
Expected Output: [[4, 5], [2, 3], [1]]
Explanation: Source Example 2: 4 and 5 come from different parents but share depth 2, so they share one inner list; the root's level is last.
Hints
- A None entry fills a child slot of some existing node but has no child slots of its own, so an entry's index alone does not tell you who its parent is.
- Each node is exactly one level deeper than its parent; once you know every node's depth, the answer is the values grouped by depth in the requested order.
- A tree with 10^4 nodes can be a single chain of height 10^4.