Threshold Level in Binary Tree

You are given a binary tree and an integer threshold. The binary tree is represented in a level-order manner, where missing nodes are denoted by the string null. Your task is to perform a level-order (breadth-first) traversal of the tree and, for each level, compute the difference between the maximum and minimum values. You must output the level (starting from 0) at which this difference exceeds the given threshold. If no such level exists, output -1.

Note: The level-order input representation is a single line of space separated values (after the threshold) where each value corresponds to a node. Use null (without quotes) for missing nodes.

The algorithm should be efficient and must correctly build the tree from the input and compute the required level using a breadth-first strategy.

inputFormat

The input consists of two lines:

1. The first line contains a single integer threshold.
2. The second line contains the level-order representation of the binary tree. Each token is either an integer or the string null (to represent a missing node), separated by spaces.

For example:

4
5 3 8 1 4 7 9

outputFormat

Output a single integer representing the first level (0-indexed) where the difference between the maximum and minimum values exceeds the given threshold. If no such level exists, output -1.

4
5 3 8 1 4 7 9

1