Show problems as
Classic problem #107MediumTreeBreadth-First SearchBinary Tree

Binary Tree Level Order Traversal II

Real-world version: Reading A Binary Tree Deepest Level First
Tracked in this browser only
Read Binary Tree Level Order Traversal II on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstTraversal & Search · Binary Trees & BST, animated step by step

A binary tree arrives as nodes, a flat list written down by walking the tree one level at a time from left to right.

  • nodes[0] holds the root's value.
  • After that the list carries two slots for every node already written down, taken in the same order those nodes were written: first that node's left child, then its right child.
  • A slot holding null means the child is absent. An absent child is not a node, so it claims no slots of its own further down the list.
  • Slots at the very end of the list may be left off when every one of them would be null.
  • An empty list means the tree has no nodes.

So [4, null, 6, 2] describes a root of 4 whose left child is absent, whose right child is 6, and whose grandchild 2 is the left child of 6.

Return the values of the tree grouped by level, with the deepest level first and the root's level last. Within each group the values run left to right. For a tree with no nodes return an empty list.

Examples

Example 1

Input
nodes = [5, null, 8, 1, 4]
Output
[[1, 4], [8], [5]]

The root is `5`, its left slot is `null` and its right child is `8`. The next two slots belong to `8`, giving it a left child `1` and a right child `4`. Taking the levels from the deepest upward gives `[1, 4]`, then `[8]`, then `[5]`.

Example 2

Input
nodes = [6, 2, 9, null, 7]
Output
[[7], [2, 9], [6]]

The root `6` has children `2` and `9`. The four slots of the level below belong to `2` and then `9`, and the list supplies only two of them, so `2` has no left child and a right child `7` while `9` has none. The deepest level is `[7]`, above it `[2, 9]`, and the root's level last.

Example 3

Input
nodes = [42]
Output
[[42]]

The tree is a single root with both child slots left off the end of the list, so there is one level to report.

Constraints

  • 0 <= nodes.length <= 4001
  • -1000 <= nodes[i] <= 1000
  • The tree holds between 0 and 2000 nodes.
  • Every entry of nodes is either an integer or null, and nodes[0] is never null.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def levels_deepest_first(nodes: list) -> list[list[int]]:
Java
public List<List<Integer>> levelsDeepestFirst(Integer[] nodes)

More on the same topics