Binary Tree Operations

You are given a series of integer values which must be inserted into a binary search tree. The binary search tree (BST) is defined with the following properties:

• All keys in the left subtree of a node are less than the node's key.
• All keys in the right subtree of a node are greater than the node's key.
• If an insertion is attempted for a duplicate key, it is ignored.

After building the BST, you are required to compute and output:

1. The in-order traversal (i.e. sorted order) of the tree.
2. The pre-order traversal of the tree.
3. The post-order traversal of the tree.
4. The height of the tree. The height of an empty tree is defined as 0 and the height of a non-empty tree is \(1+\max(\text{height of left subtree},\ \text{height of right subtree})\).
5. A check whether the tree is balanced. A binary tree is considered balanced if, at every node, the height difference between the left and right subtrees is at most 1. Print YES if balanced and NO otherwise.

Input/Output Format: The input is read from standard input and the output is written to standard output.

inputFormat

The first line of input contains an integer \(n\) (\(n \ge 0\)) representing the number of keys to be inserted into the BST.

The following \(n\) lines each contain an integer key. You can assume that all keys provided are valid integers.

outputFormat

Output five lines:

1. First line: In-order traversal (space-separated integers). If the tree is empty, output a blank line.
2. Second line: Pre-order traversal (space-separated integers). If the tree is empty, output a blank line.
3. Third line: Post-order traversal (space-separated integers). If the tree is empty, output a blank line.
4. Fourth line: The height of the BST.
5. Fifth line: YES if the BST is balanced; otherwise, NO.

## sample

0

0
YES

</p>