Height Balanced Tree

Given the root of a binary tree, return whether its height is balanced. That is, for every node in the tree, the absolute difference of the height of its left subtree and the height of its right subtree is 0 or 1.

Constraints

• n ≤ 100,000 where n is the number of nodes in root

https://binarysearch.com/problems/Height-Balanced-Tree

Examples

Example 1

Input

• root =

Output

• answer = True

Example 2

Input

• root =

Output

• answer = False

Explanation

This is false since the root’s right subtree has height of 2, and left has height of 0.

Solution