Height Balanced Binary Tree

Given a pointer to the root node of a binary tree, return true if the binary tree is height balanced.

A height-balanced binary tree is a Binary tree in which the difference between the left subtree height and the right subtree height is at most 1.

Height of a binary tree is the number of edges between the root node to the longest leaf node.

NOTE: If the root node is height balanced in a binary tree, that does not ensure that the entire binary tree is height balanced.

Example

Input binary tree

Output

true

Explanation

At any point or node in the given binary tree, the maximum difference of the height does not exceed 1. That is, Height(left subtree) - Height (right subtree) <= 1 at all the nodes.

Example

Input binary tree

Output

false

Explanation

Consider node 5: The height of the Right subtree is 2 and the height of the Left subtree is 0. The difference comes out to be 2. Hence the given binary tree is not height balanced.

Constraints

Constraints

• The number of nodes in the tree is in the range [1, 104].
• -105 <= Node.val <= 105