Quick 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.

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

Given a binary tree, return its node values level by level, starting from the deepest level and ending with the root's level. Within each level, list the values from left to right. The report names this task only by reference, next to another tree task in the same round; this version states the standard task in full. ### Function Signature ```python def levels_bottom_up(tree: list[int | None]) -> list[list[int]]: ``` ### Rules - `tree` is the level-order (breadth-first, left to right) listing of the nodes. Each existing node's two child slots appear in order, with `None` for a missing child; a missing node has no child slots. Trailing `None` entries may be omitted. An empty tree is `[]`; otherwise `tree[0]` is the root and is never `None`. - The root is at depth 0, and each child is one level deeper than its parent. - Return one list per depth that contains at least one node, ordered from the greatest depth down to depth 0. Each inner list holds that depth's values in left-to-right order. - For an empty tree, return `[]`. ### 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. ### Examples **Example 1** ```text Input: tree = [3, 9, 20, None, None, 15, 7] Output: [[15, 7], [9, 20], [3]] ``` ```text 3 / \ 9 20 / \ 15 7 ``` **Example 2** ```text Input: tree = [1, 2, 3, 4, None, None, 5] Output: [[4, 5], [2, 3], [1]] ``` ```text 1 / \ 2 3 / \ 4 5 ``` Nodes 4 and 5 hang from different parents but are both at depth 2, so they share one inner list. **Example 3** ```text Input: tree = [] Output: [] ```

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.

Given a binary tree, return its node values level by level, starting from the deepest level and ending with the root's level. Within each level, list the values from left to right. **Input encoding.** `tree` is the level-order (breadth-first, left to right) listing of the nodes. Each existing node's two child slots (left, then right) appear in order, with `None` for a missing child; a missing node has no child slots. Trailing `None` entries may be omitted. An empty tree is `[]`; otherwise `tree[0]` is the root and is never `None`. In JavaScript a missing child is `null`; in Java `tree` is a `java.util.List<Integer>` with `null` entries; in C++ `tree` is a `std::vector<std::optional<int>>` with `std::nullopt` entries. **Output.** The root is at depth 0, and each child is one level deeper than its parent. Return one list per depth that contains at least one node, ordered from the greatest depth down to depth 0. Each inner list holds that depth's values in left-to-right order. For an empty tree, return `[]`. Every value fits in a 32-bit signed integer; no value can exceed 2^31-1. **Example 1** ``` Input: tree = [3, 9, 20, None, None, 15, 7] Output: [[15, 7], [9, 20], [3]] ``` The root 3 has children 9 and 20; 9 is a leaf, and 20 has children 15 and 7. **Example 2** ``` Input: tree = [1, 2, 3, 4, None, None, 5] Output: [[4, 5], [2, 3], [1]] ``` Nodes 4 and 5 hang from different parents but are both at depth 2, so they share one inner list. **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.

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

  1. 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.
  2. 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.
  3. A tree with 10^4 nodes can be a single chain of height 10^4.

Binary Tree Levels from the Deepest Up

mediumGoogleSoftware Engineer

Given a binary tree, return its node values level by level, starting from the deepest level and ending with the root's level. Within each level, list the values from left to right.

Input encoding. tree is the level-order (breadth-first, left to right) listing of the nodes. Each existing node's two child slots (left, then right) appear in order, with None for a missing child; a missing node has no child slots. Trailing None entries may be omitted. An empty tree is []; otherwise tree[0] is the root and is never None.

In JavaScript a missing child is null; in Java tree is a java.util.List<Integer> with null entries; in C++ tree is a std::vector<std::optional<int>> with std::nullopt entries.

Output. The root is at depth 0, and each child is one level deeper than its parent. Return one list per depth that contains at least one node, ordered from the greatest depth down to depth 0. Each inner list holds that depth's values in left-to-right order. For an empty tree, return []. Every value fits in a 32-bit signed integer; no value can exceed 2^31-1.

Example 1

Input:  tree = [3, 9, 20, None, None, 15, 7]
Output: [[15, 7], [9, 20], [3]]

The root 3 has children 9 and 20; 9 is a leaf, and 20 has children 15 and 7.

Example 2

Input:  tree = [1, 2, 3, 4, None, None, 5]
Output: [[4, 5], [2, 3], [1]]

Nodes 4 and 5 hang from different parents but are both at depth 2, so they share one inner list.

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.

Examples

Example 1
Input
([3, 9, 20, None, None, 15, 7],)
Output
[[15, 7], [9, 20], [3]]
Notes
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.
Example 2
Input
([1, 2, 3, 4, None, None, 5],)
Output
[[4, 5], [2, 3], [1]]
Notes
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.

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.

Comments (0)

No comments yet. Be the first to comment!

Submit your answer

Approved first answer today earns 30 XP
Bold⌘BItalic⌘IInline code⌘`Bullet listTab to nest (○ ■)Numbered listTab to nest (a. i.)QuoteCode block
Formatting help
Signature
def levels_bottom_up(tree: list[int | None]) -> list[list[int]]:
Sample call
levels_bottom_up([3, 9, 20, None, None, 15, 7])
Language
Case 1
Input
([3, 9, 20, None, None, 15, 7],)
Expected
[[15, 7], [9, 20], [3]]
Case 2
Input
([1, 2, 3, 4, None, None, 5],)
Expected
[[4, 5], [2, 3], [1]]

Browse More Questions

Show the approach

Approach

Decode the level-order listing in a single left-to-right pass without building node objects. Keep a read pointer i over the child slots (starting at index 1) and a queue holding the depth of every existing node in the order it appears in the listing (the root has depth 0). Dequeue the next existing node of depth d; the next two unread entries are its left and right child slots. Each non-None entry is a node of depth d + 1: append its value to the list for depth d + 1 (creating that list the first time the depth is reached) and enqueue its depth. None entries are consumed but enqueue nothing, because a missing node has no child slots. Invariant: the listing is breadth-first, so when the k-th existing node is dequeued, all earlier existing nodes have already consumed exactly their two slots, and the next unread entries belong to it. Parents are dequeued left to right and each parent's left slot precedes its right, so every depth list is filled in left-to-right order. After the scan, reverse the list of depth lists so the deepest level comes first and the root's level is last. Edge cases: an empty listing returns []; omitted trailing None entries simply end the scan early, while written-out trailing None slots are consumed with no effect; 0 is a real value, so test for None rather than falsiness; the pass is iterative, so a chain of 10^4 nodes needs no recursion.

Time complexity:
O(n), where n = len(tree)
Space complexity:
O(n)