Check if a Binary Tree is Superbalanced

A binary tree is said to be superbalanced if the difference between the depths of any two leaf nodes is at most one. In other words, the tree is superbalanced if all leaves are at nearly the same depth.

You are given a binary tree in the form of a level-order traversal. The tree nodes are provided as space-separated values. The token N represents a null node (i.e., no child at that position). Your task is to determine whether the given binary tree is superbalanced.

Definition: Let the depths of any two leaf nodes be \(d_1\) and \(d_2\). The tree is superbalanced if \(|d_1 - d_2| \le 1\) for all pairs of leaf nodes.

Read the input from stdin and output your result to stdout as either True or False.

inputFormat

The input consists of a single line containing space-separated tokens representing the level-order traversal of the binary tree. Each token is either an integer or N (which indicates a null node). If the first token is N, then the tree is empty.

Example: 3 9 20 N N 15 7

outputFormat

Output a single line: True if the binary tree is superbalanced, or False otherwise.

N

True