Check Full Binary Tree

You are given a binary tree. Your task is to determine whether the given binary tree is a full binary tree.

A binary tree is considered a full binary tree if every node has either zero or two children. Formally, for every node in the tree, either both its left and right children exist or neither exists. The empty tree is also considered a full binary tree.

You will be given a single line of input, which is a level order traversal of the tree. The value null represents a missing node.

Note: If the tree is empty (represented by a single token null), it is considered a full binary tree.

The answer must be printed as either True or False.

In mathematical notation, for each node v with children l and r, the tree is full if:

\[ (v = null) \quad \text{or} \quad ((l \neq null \; \land \; r \neq null) \; \text{and} \; isFull(l) \; \land \; isFull(r)) \]

inputFormat

The input consists of a single line containing the level order traversal of the binary tree. The values are separated by spaces. Each value is either an integer or the string null (indicating a missing node).

Examples:

• 1 2 3 4 5 6 7 represents a full binary tree.
• 1 2 3 null null 6 null represents a tree where one node has only one child, which is not a full binary tree.
• null represents an empty tree.

outputFormat

Output a single line: True if the binary tree is a full binary tree, and False otherwise.

## sample

1 2 3 4 5 6 7

True