Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction-  
2.
Solution Approach 
3.
Algorithm -
4.
C++ code:
5.
Algorithm Complexity: 
6.
Frequently asked questions-
7.
Key takeaways-
Last Updated: Mar 27, 2024

Optimal Sequence for AVL Tree Insertion

Author Riya
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction-  

This blog will discuss the problem of finding an optimal sequence for AVL tree insertion. Before moving further, let’s see what an AVL Tree is.

“AVL trees, also known as self-balancing binary search trees, are a special type of binary search trees which adjust their height such that the difference of heights of left and right subtree of any node is either 0 or 1.”

Now, let’s understand the problem:

In this problem, we will be given an array of integers, and we have to find a sequence in which we should insert these integers into a binary search tree such that it will be an AVL tree without requiring any rotations to self-balance it.


Look at the following example for better understanding:

Suppose the following array of integers is given:

arr = {5, 4, 3, 2, 1}

Case 1: If we insert the integers in the given order, we will get the following binary search tree:

We can see that this binary search tree is not a balanced BST, so rotations are required to make it an AVL tree.


Case 2: If we insert the integers in the order {1, 2, 3, 4, 5}, we will get the following binary search tree:

We can see that this binary search tree is not a balanced BST, so rotations are required to make it an AVL tree.


Case 3:  If we insert the integers in the order {3, 1, 4, 2, 5}, we will get the following binary search tree:

This is a balanced binary search tree, and no rotations are required to convert it into an AVL tree.
Hence,  {3, 1, 4, 2, 5} can be the required optimal sequence for AVL tree insertion.


Now that we understand the problem let’s discuss the approach to solving it in the next section.

Solution Approach 

This section will discuss the approach to find the optimal sequence for AVL tree insertion. To find the optimal sequence for AVL tree insertion, first create a balanced binary search tree (i.e., AVL tree) using the given integers. After creating the AVL tree from the given integers, find the level order traversal of the tree. If we insert the integers in that order, then the AVL tree will be created level by level. To construct an AVL tree using the given array of integers, we can sort the integers and use a recursive function in which we will find the middle element of the array and make it root and then call the function recursively to construct the left and right subtrees with the left and right half of the array integers respectively.                     

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Algorithm -

Step 1. Create a “Node” class for constructing the trees.

Step 2. Create a function “findOptimalSequence()” which takes two inputs - sorted array of integers and size of the array, and returns the optimal sequence for AVL tree insertion. Inside this function, call a function to create an AVL tree from the sorted array and then call a function to find its level order traversal. This vector formed by level order traversal will be the optimal sequence for AVL tree insertion, so return this.

Step 3. Next, create a function “sortedArrayToAVLTree()” to construct an AVL tree from a sorted array. Inside the function, create the root of the tree with the value of the middle element and then call the function recursively to construct the left and right subtree using the first and last half of array integers, respectively.  

Step 4. Finally, create a function “levelOrderTraversal()”, which will take the root of the binary tree and return its level order traversal.

C++ code:

// C++ program to find optimal sequence for AVL tree insertion
#include <bits/stdc++.h>
using namespace std;


// Node class to create tree
class Node {
public:
int data;
Node* left;
Node* right;

Node(int val) {
data = val;
left = NULL;
right = NULL;
}
};


//Function to construct AVL tree from a sorted array 
Node* sortedArrayToAVLTree(int arr[], int start, int end)
{


// Base Case
if (start > end) {
return NULL;
}


// Get the middle element and make it root 
int middle = (start + end) / 2;
Node* root = new Node(arr[middle]);


// Call the function recursively to construct the left subtree
root->left = sortedArrayToAVLTree(arr, start, middle - 1);


      // Call the function recursively to construct the right subtree
root->right = sortedArrayToAVLTree(arr, middle + 1, end);


    // Return the root of the tree
return root;
}


// Function to find the level order traversal
vector<int> levelOrderTraversal(Node *root)
{
vector<int> levelOrder;

queue<Node*> q;

if(root!=NULL) {
q.push(root);
}


while (!q.empty())
{
Node* curr_node = q.front();
q.pop();

levelOrder.push_back(curr_node->data);

if (curr_node->left) {
q.push(curr_node->left);
}
if (curr_node->right) {
q.push(curr_node->right);
}
}

    return levelOrder;
}


// Function to find the optimal sequence for AVL tree insertion
vector<int> findOptimalSequence(int arr[], int n)
{


   // Calling a function to construct an AVL tree using the sorted array
   Node* root = sortedArrayToAVLTree(arr, 0, n-1);
  
   // Calling a function to find the level order traversal of the AVL tree
   vector<int> optimalSequence = levelOrderTraversal(root);
  
   return optimalSequence;
}


// Main function
int main()
{


    // Given size of the array
    int n = 5;
    
    // Given array
int arr[5] = {4, 3, 2, 5, 1};

    // sort the given array
    sort(arr, arr+n);
    
    // Call the function to find the optimal sequence for AVL tree insertion
    vector<int> optimalSequence = findOptimalSequence(arr, n);

    // Print the optimal sequence
    for(int i=0; i<n; i++)
    {
  cout<<optimalSequence[i]<<" ";
    }


return 0;
}

 

Output:
3 1 4 2 5 

 

Algorithm Complexity: 

Time Complexity: O(N * log(N))

In the above approach to find an optimal sequence for AVL tree insertion, first, we have sorted the array which takes O(N * log(N)) time and then constructed the AVL tree, which takes O(N) time, and finally, the level order traversal which takes O(N) time. So, the overall time complexity is O(N * log(N)), where ‘N’ is the number of integers in the given array.

Space Complexity: O(N) 

In the above approach to find an optimal sequence for AVL tree insertion, we have constructed an AVL tree that takes O(N) space, and the vector to store the level order traversal also takes O(N) space. So, the overall space complexity is O(N), where ‘N’ is the number of integers in the given array.

Frequently asked questions-

  1. What is a Binary Search Tree?

BST (Binary Search Tree) is a special binary tree in which there is a condition that all the nodes in the left subtree of any node will have a value less than that of the node, and all the nodes in the right subtree of the node will have a value greater than the value of the node.

2. What is an AVL Tree?

AVL trees, also known as self-balancing binary search trees, are a special type of binary search trees that adjust their height such that the difference of heights of left and right subtree of any node is either 0 or 1

 

Key takeaways-

IThis article discussed the problem “Optimal sequence for AVL tree construction”, the solution approach to this problem, its C++ implementation, and its time and space complexity. If you want to solve more problems on tree data structure for practice, you can visit Coding Ninjas Studio.


If you think that this blog helped you share it with your friends!. Refer to the DSA C++ course for more information.
Check out this problem - Largest BST In Binary Tree


Until then, All the best for your future endeavors, and Keep Coding.

Previous article
Find the largest K for every Array element such that at least K prefixes are ≥ K.
Next article
Count Inversions in an Array Using AVL Tree
Live masterclass