Check if Binary Tree is Height-Balanced

You are given a binary tree in the form of a level order traversal. The tree is represented as a list of integers, where the value -1 denotes a null node. A binary tree is height-balanced if for every node in the tree, the difference between the heights of the left and right subtrees is no more than one. Formally, for every node, if h_left and h_right are the heights of the left and right subtrees respectively, then the tree is balanced if:

\(|h_{left} - h_{right}| \le 1\)

Your task is to rebuild the binary tree from its level order representation and determine whether it is height-balanced.

The level order is constructed as follows: the root is at index 0, then the left child of the node at index i is at index 2i+1 and the right child is at index 2i+2. If a value is -1, that position in the tree is considered a null node.

inputFormat

The input is a single line containing space-separated integers representing the level order traversal of the binary tree. A value of -1 represents a null node. For example:

3 9 20 -1 -1 15 7

If the input is empty, consider it as an empty tree.

outputFormat

Output a single line: True if the binary tree is height-balanced, and False otherwise.

3 9 20 -1 -1 15 7

True