Balanced Binary Tree Check

You are given a binary tree and your task is to determine whether the tree is height-balanced. A binary tree is balanced if for every node in the tree, the absolute difference between the height of its left subtree and right subtree is at most 1. The height of an empty tree is defined as 0, and an empty tree is considered balanced.

Definition (in LaTeX):

\( |h(left)-h(right)| \le 1 \)

The input will describe the binary tree using an array-like representation. Each node is given by three integers: value, left_index, right_index. The indices are 0-indexed and the root is always the node at index 0. If a child does not exist, its index will be -1.

Your program should read the input from stdin and output the result to stdout. Print True if the tree is balanced and False otherwise.

inputFormat

The input is given as follows:

N
val_0 left_0 right_0
val_1 left_1 right_1
... 
val_{N-1} left_{N-1} right_{N-1}

Where N is the number of nodes in the tree. Each of the following N lines contains three integers. For each node, val is its value (can be ignored by your algorithm), and left and right denote the indices of its left and right child respectively (or -1 if it doesn’t exist). If N is 0, the tree is empty.

outputFormat

Output a single line with either True if the tree is balanced or False otherwise.

## sample

7
1 1 2
2 3 4
3 5 6
4 -1 -1
5 -1 -1
6 -1 -1
7 -1 -1

True