A binary tree of building-floor sensor ids is given in level-order form (a single line of space-separated tokens, null marking a missing child; every non-null node contributes exactly two following tokens for its children). The tree always has at least one node.
Define a node's height as the number of edges on the longest path from that node down to a leaf in its subtree (a leaf has height 0). The tree is height-balanced if, for every node in the tree, the heights of its left and right subtrees differ by at most 1 (treat a missing child as height -1, so that a leaf has height 0).
Formally: define height(missing child) = -1, and height(node) = 1 + max(height(left), height(right)). The tree is balanced if, at every node, |height(left) - height(right)| <= 1 (again using -1 for a missing child).
If the tree is height-balanced, print its overall height (height(root)). Otherwise, print -1.
Input format
Line 1: space-separated level-order tokens describing the binary tree (integers and the token null). The tree has at least 1 node.
Output format
A single integer: the tree's height if it is height-balanced, otherwise -1.
Constraints
- 1 <= number of nodes <= 500
- Each node value is an integer with -1000 <= value <= 1000