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

Binary Tree Level Order Traversal

Real-world version: Cable Splice Depths
Tracked in this browser only
Read Binary Tree Level Order Traversal on LeetCode(opens in a new tab)

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

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

A fibre trunk fans out through a set of splice enclosures. One enclosure sits at the head of the run, and every enclosure passes the fibre on to at most two enclosures further out: one wired to its left tray and one wired to its right tray. Each enclosure is labelled with a signed loss figure in hundredths of a decibel.

Because the harness passes plain JSON, the run arrives as the array splices, written out depth by depth. splices[0] is the loss figure at the head enclosure. After it the entries come in pairs, giving the left tray and then the right tray of each enclosure already written out, taken in that same order. An empty tray is written null, and a null claims no pair of its own. Trailing null entries are left off the end, and an empty array means no enclosures were fitted.

The depth of the head enclosure is 0, and an enclosure wired to a tray of a depth-d enclosure sits at depth d + 1.

Return a list whose i-th entry is the list of loss figures of every enclosure at depth i, each depth given in the order those enclosures appear in splices. Return an empty list when no enclosures were fitted.

Examples

Example 1

Input
splices = [4, -7, 12, null, 5]
Output
[[4], [-7, 12], [5]]

The head enclosure reads 4. Its two trays carry -7 and 12, so depth 1 holds both figures in that order. The left tray of the -7 enclosure is empty and its right tray carries 5, the only enclosure at depth 2.

Example 2

Input
splices = [0]
Output
[[0]]

One enclosure was fitted and it reads 0, so depth 0 is the only depth reported.

Example 3

Input
splices = [-3, null, 8, 6, -1]
Output
[[-3], [8], [6, -1]]

The head enclosure has an empty left tray, so the entry 8 belongs to its right tray. The 8 enclosure is then the next one written out, and the pair 6 and -1 fills its two trays at depth 2.

Constraints

  • 0 <= number of enclosures <= 2000
  • -1000 <= loss figure <= 1000
  • 0 <= splices.length <= 4001
  • Every entry of splices is either null or an integer loss figure
  • splices[0] is a loss figure whenever splices is non-empty

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 splice_depths(splices: list) -> list[list[int]]:
Java
public List<List<Integer>> spliceDepths(Integer[] splices)

More on the same topics