Delete a node from AVL tree

Easy
0/40
Average time to solve is 10m
0 upvote
Asked in companies
AckoOYOAmdocs

Problem statement

Given an AVL tree,delete an element in the AVL Tree.

An AVL tree is a self-balancing binary search tree.

It has the following properties:

It has the property of the binary search tree , i.e for every node , the nodes in its left subtree is less than the node and the node in the right subtree is greater than the current node.

The absolute difference between the height of left subtree and right subtree of any node is less than or equal to 1.

Read more about AVL Tree Here: https://en.wikipedia.org/wiki/AVL_tree

Note 
1. Do not print anything, just return the root node of the tree.
2. Your constructed tree will be checked by doing an in-order traversal of the tree from the returned root node.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
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 deleted.

If any node does not have a 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 :

example

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).
Note : 
The above format was just to provide clarity on how the input is formed for a given tree.

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
Output Format 
For each test case, the root node of the AVL tree with the given node inserted.
Constraints: 
1 <= T <= 100
1<= N <= 3*10^3

Where ‘T’ is the total number of test cases and N denotes the number of nodes in the given binary tree.

Time limit: 1 second
Sample Input 1:
2
15 12 20 10 14 -1 -1 -1 -1 -1 -1 
20
50 20 60 -1 -1 -1 -1 
60
Sample Output 1:
10 12 14 15
20 50
Explanation of sample input 1 :
Test Case 1:

Initially, the tree is:


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 15 it is 1 (height of left subtree is 2 and right subtree is 1.)
For node 12 it is 0 (height of left subtree is 1 and right subtree is 1.)
For node 10 it is 0 (height of left subtree is 0 and right subtree is 0.)
For node 14 it is 0 (height of left subtree and right subtree is 0.)
For node 20 it is 0 (height of left subtree is 0 and right subtree is 0.)

After deleting 20 using the standard deletion procedure we get:


We can clearly see that the node with value 15 is imbalanced as it has balance factor 2.

After rebalancing we get:


Now this final tree is balanced as all the nodes have the balance factor less than or equal to 1.

We return the root node of the balanced AVL Tree and can verify that the in-order traversal of the AVL tree will be:{10 14 12 15 }

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.)
For node 60 it is 0(height of left subtree is 0 and right subtree is 0.)


After deleting, 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.)


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}.
Sample Input 2:
2
5 1 4 -1 -1 -1 -1
1
1 2 3 -1 -1 -1 4 -1 -1 
3
Sample Output 2:
5 4
2 1 4
Hint

Find node and delete then rebalance the tree

Approaches (1)
Standard Approach
  • The idea is to delete 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 left child of left subtree, then you perform a 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.


 

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

  • Delete 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 delete remains same as BST delete 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 stack, therefore, the space complexity is of the order of ‘n’

Code Solution
(100% EXP penalty)
Delete a node from AVL tree
Full screen
Console