AVL Tree: Insert

The first line contains an Integer 't' which denotes the number of test cases or queries to be run. Then the test cases follow. The first line of input contains the elements of the tree in the level order form separated by a single space. The second line contains an integer denoting the value to be inserted If any node does not have left or right child, take -1 in its place. Refer to the example below. Example: Elements are in the level order form. The input consists of values of nodes separated by a single space in a single line. In case a node is null, we take -1 on its place. For example, the input for the tree depicted in the below image would be :

1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1 Explanation : Level 1 : The root node of the tree is 1 Level 2 : Left child of 1 = 2 Right child of 1 = 3 Level 3 : Left child of 2 = 4 Right child of 2 = null (-1) Left child of 3 = 5 Right child of 3 = 6 Level 4 : Left child of 4 = null (-1) Right child of 4 = 7 Left child of 5 = null (-1) Right child of 5 = null (-1) Left child of 6 = null (-1) Right child of 6 = null (-1) Level 5 : Left child of 7 = null (-1) Right child of 7 = null (-1) The first not-null node (of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on. The input ends when all nodes at the last level are null (-1).

1.The above format was just to provide clarity on how the input is formed for a given tree. 2.The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as: 1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

We can see that the given Tree is an avl tree because for each node in the tree, the balance factor is less than 1. For node 10 it is 0 (height of left subtree and right subtree is 0.) For node 20 it is 1 (height of left subtree is 1 and right subtree is 0.) For node 50 it is 1 (height of left subtree is 2 and right subtree is 1.) For node 60 it is 0 (height of left subtree and right subtree is 0.) After inserting the node the tree is:

After Inserting 8 the tree is imbalanced as: For node 10 it is 1 (height of left subtree is 1 and right subtree is 0.) For node 20 it is 2 (height of left subtree is 2 and right subtree is 0.) For node 50 it is 2 (height of left subtree is 3 and right subtree is 1.) For node 60 it is 0 (height of left subtree and right subtree is 0.) The imbalance closest to the newly added node is at node 20. Now this occurs because of insertion in the left subtree of the left child so we need a right rotation to balance it. The Balanced AVL tree is:

After balancing, the balance factors are as follows: For node 10 it is 0 (height of left subtree 1 and right subtree is 1.) For node 20 it is 0 (height of left subtree is 0 and right subtree is 0.) For node 50 it is 1 (height of left subtree is 2 and right subtree is 1.) For node 60 it is 0 (height of left subtree and right subtree is 0.) We see that now all balance factors are less than or equal to 1 therefore the Tree is now balanced and hence an AVL tree. We return the root node of the balanced AVL Tree and can verify that the in-order traversal of the AVL tree will be:{8 10 20 50 60 } Test Case 2: Initially, the tree is:

The Balance Factor are: For node 20 it is 0 (height of left subtree is 0 and right subtree is 0.) For node 50 it is 1 (height of left subtree is 1 and right subtree is 0.) After inserting, the tree is:

The balance Factor are: For node 20 it is 0 (height of left subtree is 0 and right subtree is 0.) For node 50 it is 0 (height of left subtree is 1 and right subtree is 1.) For node 60 it is 0(height of left subtree is 0 and right subtree is 0.) Since this tree is already balanced, we return the root node of the tree and can verify that the in-order traversal will be {20,50,60}.

Recursive insertion approach

The idea is to insert the node as we do in a traditional BST and then go up the tree to find the first point of imbalance, i.e the place where the balance factor of the node is greater than or equal to two.
Balance factor of a node is defined as the absolute difference between the number of nodes of the Left Subtree and the right subtree.
If, for all the nodes from the newly inserted node to the root node of the tree, the balance factor is 0 1 or -1 the tree is already balanced and we do not need to do anything.
Otherwise, 4 cases may arise which are as follows:
- If there is an imbalance in the right child of the left subtree, then you perform a left-right rotation.

If there is an imbalance in the right child of right subtree, then you perform a left rotation.

If there is an imbalance left child of the right subtree then you perform a right-left rotation

If there is an imbalance in the left child of left subtree, then you perform a right rotation.

Keeping in mind the above idea, we can devise the following recursive approach:

Insert the node in the tree as we do in a traditional BST and update the height of all of the ancestors of the newly inserted node.
While Calculating the height, Also calculate the balance factor of the ancestors, which is the difference in the height of left subtree and right subtree.
If the Balance Factor is greater than 1 we either need to do a left left rotation or left right rotation.
If it is a left left case, the newly inserted node will be in the left child of the left subtree of the current node, i.e it will be less than the left child of the current node. Otherwise, it is the left right case.
To do a left rotate, let us assume that we do it at a node ‘x’ then we define 2 variables, ‘rightSubTreeRoot’ which is the right node of the current node and also the root of the right subtree.Also we define another variable ‘rightSubTreeRootLeftChild’ which is the left child of the node which is the right child of the current node.
To perform the left rotation, we connect the left of the ‘rightSubTreeRoot’ to ‘x’ and connect the right of ‘x’ to ‘rightSubTreeRootLeftChild’
Then we update the heights and return the ‘rightSubTreeRoot’ as root of the rotated tree.
In a similar way, if the balance factor is less than -1 we need to do right left rotation or right right rotation.
If it is a right right case, the newly inserted node will be the in the right child of the right subtree of the current node, i.e it will be greater than the right child of the current node. Otherwise, it is the right left case.
To do a right rotate, let us assume that we do it at a node ‘x’ then we define 2 variables, ‘leftSubTreeRoot’ which is the left node of the current node and also the root of the left subtree.Also we define another variable ‘leftSubTreeRootRightChild’ which is the right child of the node which is the left child of the current node.
To perform the right rotation, we connect the right of the ‘leftSubTreeRoot’ to ‘x’ and connect the left of ‘x’ to ‘leftSubTreeRootRightChild’
Then we update the heights and return the ‘leftSubTreeRoot’ as root of the rotated tree.
We perform the suitable rotations and update the heights of the nodes to check other nodes of the tree until we reach the root.
The other 2 cases are just combinations of left and right rotate.

Time Complexity

O(log(n)), where ‘n’ is the number of nodes in the tree.

The rotation operations (left and right rotate) take constant time as only a few pointers are being changed there. Updating the height and getting the balance factor also takes constant time. So the time complexity of AVL insert remains same as BST insert which is O(h) where h is the height of the tree. Since the AVL tree is balanced, the height is O(Logn). So time complexity of AVL insert is O(Logn).

Space Complexity

O(n), where ‘n’ is the number of nodes in the tree.

In the worst case, we can have ‘n’ elements in the recursive stack, therefore, the space complexity is of the order of ‘n’

Problem statement

Sample Input 1:

Sample Output 1:

Explanation of sample input 1 :

Sample Input 2:

Sample Output 2: