Problem Statement:

You're building a smart phone contact manager app that must support fast insertions and lookups. Since the contacts can grow rapidly and must stay balanced for efficient access, you're asked to implement an AVL Tree for storing names.

After inserting all contact names into the AVL Tree, your task is to output the in-order traversal of the final balanced tree.

An AVL Tree is a self-balancing Binary Search Tree (BST) that maintains the height difference between left and right subtrees ≤ 1 for every node.

Input:

• contacts: A list of strings representing names to insert, in the given order.

Output:

Return the in-order traversal of the AVL Tree after all insertions.

Constraints:

• 1 ≤ contacts.length ≤ 10⁴
• All contact names are lowercase non-empty alphabetic strings (max 20 characters)
• No duplicate names

Example 1:

input: [leo, anna, zoe, max]
output: [anna, leo, max, zoe]

Explanation:
Names are inserted into an AVL tree and rebalanced as necessary. In-order traversal yields sorted names.
    

Example 2:

input: [carl, bob, adam]
output: [adam, bob, carl]

Explanation:
After balancing the tree through left-right rotations, in-order traversal returns names in sorted order.
    

Example 3:

input: [nina]
output: [nina]

Explanation:
Only one name inserted. No rotation needed. In-order is the single name.
    

Example 4:

input: [sara, tom, lucy, mark, jack]
output: [jack, lucy, mark, sara, tom]

Explanation:
AVL rebalancing results in the sorted in-order list of names.