334. Is the Tree Balanced
Print Yes if the tree is height balanced, meaning that at EVERY node the
heights of the two subtrees differ by at most 1. Print No otherwise.
The condition applies at every node, not just the root. A tree can have subtrees of equal height at the top and be badly unbalanced somewhere below.
The natural solution computes a height at each node and compares, which re-walks the same subtrees and is quadratic. The linear version computes the height once per node on the way back up and records the failure as it goes, which is the same shape as the diameter in the previous problem.
Constraints - `1 ≤ n ≤ 100000` - `-1000000000 ≤ value ≤ 1000000000` - The input always forms a valid tree rooted at node 1.
Input
The first line contains an integer n, the number of nodes.
The second line contains n values, where node i holds the ith value.
Each of the next n lines contains two integers, the left and right child of
node i, using 0 for no child. Node 1 is the root.
Output
Print Yes or No on one line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.