AVL Tree Insertion Problem

Given an AVL tree, your task is to insert an element into the AVL Tree ensuring it remains balanced.

An AVL tree is a self-balancing binary search tree with the following properties:

1. For every node, the nodes in its left subtree are less than the node, and nodes in the right subtree are greater than the node.
2. The absolute difference between the height of the left subtree and the right subtree of any node is less than or equal to 1.

Read more about AVL Trees here.

Example:

Input:

t = 1
level-order elements = 1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1
value to insert = 7

Output:

Returns the root node of the adjusted AVL tree

Constraints:

• 1 ≤ T ≤ 100
• 1 ≤ N ≤ 3 * 103
• The time limit is 1 second.

Note:

• Do not print anything; just return the root node of the AVL tree.
• The correctness of your implementation will be verified through in-order traversal of the final tree from the returned root node.

The input for each test case begins with a single integer 't' denoting the number of test cases. The first line of each test case provides the elements of the tree in level-order, separated by single spaces. The second line contains an integer value to be inserted. Use '-1' to denote a missing node.

Output Format

For each test case, return the root node of the modified AVL tree after the element has been inserted.