Peel the Leaves Round by Round

Medium

You are given the root of a non-empty binary tree. The tree is taken apart in rounds: each round removes all current leaves (nodes with no children) at once. Their parents may then become leaves themselves and go in the next round. This repeats until the tree is empty. Return the list of rounds: for each round, the values of the nodes removed in it, listed left to right as they appear in the tree.

Example 1

root=tree_node([7, 3, 8, None, 5, 6]) → [[5, 6], [3, 8], [7]]

First the leaves 5 and 6 go. Once they are gone, 3 and 8 become leaves, and finally only the root 7 is left.

Example 2

root=tree_node([1, 2, None, 3]) → [[3], [2], [1]]

The tree is a chain, so each round removes exactly one node from the bottom.

Example 3

root=tree_node([-4]) → [[-4]]

Constraints

The tree has between 1 and 100 nodes
-100 ≤ node value ≤ 100

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search Binary Tree

Similar problems

Is It a Search Tree? Medium Two Mixed-Up Nodes Medium All Leaf Paths With a Given Total Medium Tree Into a Right Chain Medium Digit Branch Totals Medium

Input

root=tree_node([7, 3, 8, None, 5, 6])

Expected

[[5, 6], [3, 8], [7]]

Run checks the first 3 tests in your browser. Submit checks all 95 tests on the server, hidden ones included.