Balanced Binary Tree Check

Given a binary tree, determine whether it is height-balanced. A binary tree is defined as balanced if for every node, the absolute difference between the height of its left subtree and its right subtree is at most \(1\), i.e. \(|h_{left} - h_{right}| \le 1\). The tree is provided as a list of node values and a list of edges. The first element in the node values list is the root. For every parent node, the first child encountered becomes its left child and the second becomes its right child.

inputFormat

The input is given from standard input (stdin) with the following format:

1. The first line contains a single integer \(n\) representing the number of nodes.
2. If \(n > 0\), the second line contains \(n\) space-separated integers representing the node values.
3. The third line contains an integer \(m\) which represents the number of edges.
4. Each of the following \(m\) lines contains two integers \(p\) and \(c\) describing an edge from node \(p\) (parent) to node \(c\) (child).

If \(n = 0\), the tree is empty and is considered balanced.

outputFormat

Output a single line to standard output (stdout) containing "YES" if the binary tree is balanced, and "NO" otherwise.

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

YES