Balanced Binary Tree

Problem statement

A directory service uses a binary tree and audits whether its branches remain height-balanced. The audit must examine the entire layout, since a balanced-looking entrance can still conceal an unbalanced branch farther down. Your task Return true exactly when, at every node, the heights of its left and right subtrees differ by at most one. A subtree height is its longest downward path measured in nodes. Important details An absent subtree has height zero. Empty trees and leaves are balanced. It is not sufficient to compare only the root branches or the number of nodes on each side; every descendant must pass the height check. Worked example A chain of three nodes has root subtree heights 2 and 0. Their difference is 2, so the layout is not balanced and the answer is false.

Input format

The first line contains n. The next n lines contain value left right for nodes 0 through n-1. Child indices are -1 when absent. Node 0 is the root when n > 0. The records form one valid binary tree; n = 0 represents an empty tree.

Output format

Print true if the condition holds, otherwise false.

Constraints

0 <= n <= 2000; -1000 <= value <= 1000. Child indices are -1 or valid node indices; no cycles or shared children.

Sample input

3
1 1 -1
2 2 -1
3 -1 -1

Sample output

false