Balanced Binary Tree Verification

In this problem, you are given a binary tree described by its node values and edges. The tree is constructed in a simple manner: the first node in the list is the root, and for each edge provided as a triple (u, v, w) the child is attached to the parent node u as the left child if available, otherwise as the right child. The weight w is given but does not affect the structure beyond the order of children assignment. Your task is to determine whether the resulting binary tree is height-balanced.

A binary tree is said to be balanced if for every node, the absolute difference between the heights of the left and right subtrees is at most 1. In mathematical terms, for every node:

You need to read the input from stdin and write your answer to stdout. If the tree is balanced, output Balanced; otherwise, output Not Balanced.

inputFormat

The input consists of multiple lines:

• The first line contains an integer N representing the number of nodes in the tree.
• The second line contains N space-separated integers representing the node values. If N = 0, this line may be empty.
• The third line contains an integer M representing the number of edges.
• The next M lines each contain three space-separated integers u, v, and w where u is the value of the parent node, v is the value of the child node, and w is an integer associated with the edge (used for ordering children only).

Note: The tree is constructed by taking the first node value as the root. For each edge, the first available child position (left then right) is used.

outputFormat

Output a single line to stdout containing either Balanced if the tree is balanced, or Not Balanced otherwise.

3
1 2 3
2
1 2 1
1 3 1

Balanced