AVL Tree Insertions and In-order Traversal

You are given a sequence of integers. Insert them one by one into an initially empty AVL tree and then print the in-order traversal of the tree.

An AVL tree is a self-balancing binary search tree. The balancing condition requires that for any node, the difference in height between its left and right subtrees is at most one. The height update formula is given by: \(\text{height} = 1 + \max(\text{height of left subtree}, \text{height of right subtree})\).

Your task is to implement the AVL tree insertion and perform an in-order traversal. The in-order traversal of a binary search tree yields the elements in non-decreasing order.

inputFormat

The first line contains an integer \(n\) representing the number of elements. The second line contains \(n\) space-separated integers to be inserted into the AVL tree.

outputFormat

Output a single line with the in-order traversal of the AVL tree. The values should be space-separated.

5
3 2 1 4 5

1 2 3 4 5