Balanced Binary Tree Check

You are given a binary tree in a level-order representation as a single line of space separated tokens. Each token is either an integer or the string null (which represents a missing node). Your task is to determine whether the given tree is height-balanced.

A binary tree is balanced if for every node in the tree, the absolute difference between the heights of its left and right subtrees is at most 1, i.e.,

\( |h_{left} - h_{right}| \le 1 \)

An empty tree (with no nodes) is considered balanced.

The answer should be printed to standard output as either BALANCED or NOT BALANCED.

inputFormat

The input is provided via standard input (stdin). It consists of a single line containing the space separated tokens representing the level-order traversal of the binary tree. Use the token null to denote an absent node. An empty input corresponds to an empty tree.

outputFormat

Output a single line to standard output (stdout) containing either BALANCED if the tree is height-balanced, or NOT BALANCED if it is not.

3 9 20 null null 15 7

BALANCED