Insertion in AVL Tree

Moderate
0/80
Average time to solve is 20m
7 upvotes
Asked in companies
AmazonMorgan StanleySamsung

Problem statement

Ninja has to implement an ‘AVL_TREE’ from scratch.

He is given ‘N’ values, representing the values of nodes to be inserted. Ninja has to insert these values into the ‘AVL_TREE’ and return its root after inserting all the nodes.

Note: An ‘AVL_TREE’ is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes.

For example:

Detailed explanation ( Input/output format, Notes, Images )
Input Format 
The first line of input 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 each test case contains an integer ‘N’ which represents the number of nodes in the tree.

The next line of each test case contains ‘N’ single space-separated integers, representing the value of each node.
Output Format : 
For each test case, print the ‘AVL_TREE’ after inserting all the nodes in level order. 


Print the output of each test case in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints : 
1 <= ‘T’ <= 10
1 <= ‘N’ <= 10^4
1 <= ‘DATA’ <= 10^5

Time Limit: 1 second
Sample Input 1:
1
6
10 20 30 40 50 25
Sample Output 1:
30 20 40 10 25 50

Explanation for Sample Output 1:

For sample test case 1: 

After inserting all the node:

Sample Input 2:
1
7
33 9 53 8 21 61 11
Sample Output 2:
33 9 53 8 21 61 11

Explanation for Sample Output 2:

For sample test case 1: 

After inserting all the node:

Hint

Think of the brute force approach.

Approaches (1)
Brute Force

We have to implement ‘AVL_TREE’ from scratch and we know ‘AVL_TREE’ follows the ‘BST’ properties. So first, we insert a new node into ‘AVL_TREE’ according to the ‘BST’ properties.

 

‘BST’ property:

DATA(left) < DATA(root) < DATA(right)  for every node.

 

And the difference between heights of left and right subtrees cannot be more than one for all nodes. 

After inserting the new node in our tree according to the ‘BST’ properties our tree may be unbalanced (i.e the difference between the height of left and right subtree more than one for a node).

So for making this tree balance we have to perform some operations:

 

  1. Left Rotation.
  2. Right Rotation.

 

 

Here, T1, T2, and T3 are the subtrees of the trees.

For re-balancing the tree by performing appropriate rotations we have 4 possible cases that need to be handled.

  • Left Left case
  • Left Right case
  • Right Right case
  • Right Left case

 

Left-Left case:

Left-Right case:

Right-Right case:

Right-Left case:

 

 

Here is the algorithm:

  1. First, we insert a new node into our tree according to the standard ‘BST’ insertion.
  2. Starting from the root, we traverse the whole tree and find the unbalanced node.
  3. Then we re-balance the tree by performing appropriate rotations. We have 4 possible cases as discussed above that need to be handled.

 

 

Time Complexity

O(N * log(N))  where ‘N’ is the number of nodes in the ‘AVL_TREE’.

 

Because first, we insert the new node according to ‘BST’ insertion which takes O(log(N)) time. If after insertion our tree is unbalanced then we are performing rotations according to one of the above 4 cases which takes constant time. We are doing this amount of work for every node. So the overall time complexity is O(N * log(N)).

Space Complexity

O(log(N)) where ‘N’ is the number of nodes in the ‘AVL_TREE’.

 

Because first, we insert the new node according to ‘BST’ insertion, and then if required we are re-balancing the tree as well. The space occupied by the recursion stack is equal to the height of the tree. Since our tree is balanced so the height of the tree is log(N). Hence the space complexity is O(log(N)). 

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Insertion in AVL Tree
Full screen
Console