All problems

Widest Spread Level

Easy · tree dfs

You are given the root of a binary tree. The depth of a node is the number of edges between it and the root, so the root is on level 0, its children are on level 1, and so on.

The spread of a level is its largest value minus its smallest value. A level with a single node has a spread of 0.

Return the index of the level with the largest spread. If several levels share the largest spread, return the shallowest one (the smallest index). An empty tree has no levels, so return -1.

Examples

Example 1

Input: root = [4, 1, 9, 3, 8, null, 2]

Output: 1

Level 0 has spread 0, level 1 holds 1 and 9 (spread 8), and level 2 holds 3, 8 and 2 (spread 6). Level 1 is the widest.

Example 2

Input: root = [7, 7, 7]

Output: 0

Every level has spread 0, so the shallowest level wins the tie.

Example 3

Input: root = []

Output: -1

There are no levels at all.

Constraints