How to convert any binary search tree to an AVL tree

A Binary Search Tree is a binary tree where the nodes are arranged in a way that the left sub-tree of a particular node always contains nodes with values less than that node's value. Similarly, the right subtree of a particular node always contains nodes with values greater than that node's value.

AVL trees, on the other hand, are self-balancing binary search trees. This means that these trees can restore the balance whenever an imbalance is created via the insertion or deletion of a node(s).

Convert a BST to an AVL tree

Given any binary search tree, it is possible to balance it and convert it to an AVL tree.

To do this, there are multiple possible methods.

Simple solution

A simple solution involves traversing all the given binary search tree nodes in order. At each node, we store its value in an array and then delete it from the tree. Once the array is populated with the values of all the nodes in the tree (or once the tree becomes empty), we can iterate through the array and insert each of these values back into the tree the same way they would be inserted into an AVL tree.

This solution takes $O(N*log(N))$ time in the worst case. This is because once each of the $N$ nodes are in the array, we need to insert it back into the tree, which takes $O(log(N)$ time (since it is an AVL insertion).

Efficient solution

A more efficient solution involves the use of recursion. First, we need to store the values of all the tree's nodes in an array via in-order traversal of the tree. Since we use in-order traversal, the resulting array will be sorted.

Note: Learn more about in-order traversal.

Once we have our array, we can start the recursive part of the process. We make the value in the middle of the array the tree's root node. Once this is done, we split the array into two halves left_arr and right_arr about the middle element (excluding it). Then, we repeat the step above for both halves until left_arr and right_arr contain just one element, which becomes a leaf node (this is our base case). As the function backtracks, our balanced binary search tree gets built. The example below demonstrates how this works.

#include <iostream>
#include <vector>
using namespace std;
class Node 
{
  public:
    int value;
  Node * left_child;
  Node * right_child;
  Node() 
  {
    value = 0;
    left_child = NULL;
    right_child = NULL;
  }
  Node(int v) 
  {
    value = v;
    left_child = NULL;
    right_child = NULL;
  }
};
class binarySearchTree 
{
  public:
    Node * root;
  binarySearchTree() 
  {
    root = NULL;
  }
  int countNodes(Node *root)
  {
    if(root == NULL){
      return 0;
    }
    else
    {
      return 1 + countNodes(root->left_child) + countNodes(root->right_child);
    }
  }
  Node * insertNode(Node * root, Node * new_node) 
  {
    // inserting the node
    if (root == NULL) 
    {
      root = new_node;
      return root;
    }
    if (new_node->value < root->value) 
    {
      root->left_child = insertNode(root->left_child, new_node);
    } 
    else if (new_node->value > root->value) 
    {
      root->right_child = insertNode(root->right_child, new_node);
    } 
    // node has been inserted
    return root;
  }
  void storeNodeValues(Node* root, vector<int> &node_values) 
  { 
    if(root!=NULL)
    {
      // in-order traversal and inserting node values in an array
      storeNodeValues(root->left_child, node_values); 
      node_values.push_back(root->value); 
      storeNodeValues(root->right_child, node_values); 
    }
    return;
  } 
    
  /* Recursive function to construct binary tree */
  Node* buildTreeFromArray(vector<int> &node_values) 
  { 
    // base case 
    if (node_values.size()==0) 
    {
      return NULL;
    } 
  
    // find the middle element and make it the root
    Node *root = new Node(node_values[node_values.size()/2]); 
  
    // repeat for left_arr
    vector<int> left_arr;
    for(int i=0 ; i<node_values.size()/2 ; i++)
    {
      left_arr.push_back(node_values[i]);
    }
    root->left_child  = buildTreeFromArray(left_arr); 
   
    // repeat for right_arr
    vector<int> right_arr;
    for(int i=(node_values.size()/2)+1 ; i<node_values.size() ; i++)
    {
     right_arr.push_back(node_values[i]);
    }
    root->right_child = buildTreeFromArray(right_arr); 
  
    return root; 
  } 
     
  Node* convertBSTtoAVL(Node* root) 
  { 
    vector<int> node_values; 
    storeNodeValues(root, node_values); 
    root = buildTreeFromArray(node_values); 
    return root;
  } 
};
void prettyPrintTree(Node * r, int space) 
{
  if (r == NULL) 
  {
    return;
  }
  space += 10; 
  prettyPrintTree(r->right_child, space); 
  cout << endl;
  for (int i = 10; i < space; i++) 
  {
    cout << " ";   
  }
  cout << r->value << "\n"; 
  prettyPrintTree(r->left_child, space); 
}
int main()
{
  // creating the BST
  binarySearchTree obj;
  Node * n1 = new Node(4);
  Node * n2 = new Node(3);
  Node * n3 = new Node(2);
  Node * n4 = new Node(1);
  Node * n5 = new Node(5);
  Node * n6 = new Node(6);
  Node * n7 = new Node(7);
  obj.root = obj.insertNode(obj.root, n1);
  obj.root = obj.insertNode(obj.root, n2);
  obj.root = obj.insertNode(obj.root, n3);
  obj.root = obj.insertNode(obj.root, n4);
  obj.root = obj.insertNode(obj.root, n5);
  obj.root = obj.insertNode(obj.root, n6);
  obj.root = obj.insertNode(obj.root, n7);
  cout << "Original BST:" << endl ;
  prettyPrintTree(obj.root, 1);
  obj.root = obj.convertBSTtoAVL(obj.root) ;
  cout << "\nBST after converting it to an AVL tree:" << endl ;
  prettyPrintTree(obj.root, 1);
  return 0 ;
}

Explanation

The function convertBSTtoAVL() calls two other functions which help in executing the steps discussed above:

storeNodeValues(): This performs the in-order traversal to store all the node values in an array.
buildTreeFromArray(): This builds the tree from the array recursively.

Note: We use vectors here instead of arrays because vectors are easy to work with when the number of elements to be stored isn't known beforehand. In essence, vectors can be used for the same purposes as an array.

Time Complexity

This solution takes $O(N)$ time in the worst case. This is because, first, we store the value of each of the $N$ nodes in an array, which takes $O(N)$ time. Then, we go through each of the $N$ values in the array and make them the root node at some point during the recursive call. This step takes $O(1)$ time for each element. Hence, the total time complexity is $O(N)$ .