Introduction
A tree in which every node can have at max 2 children is known as a binary tree and a BST is a variation of a binary tree in which all of the nodes present in the left subtree are smaller than the root node and all of the nodes present in the right side of the root node are greater than the root node.
In this article, we will discuss a coding problem in which we have to convert a normal BST to a balanced BST.
Problem Statement 🧾
Ninja has given you a BST. Your task is to convert a normal BST to a balanced BST.
A binary search tree is balanced when the difference between the height of the left child and the height of the right child is not more than 1 and this property holds for every node present in the BST. For example,
Sample Examples🧐
Input
Output
Explanation
As we can see in the below image the height difference between the left and the right child for some nodes is more than 1 in our original BST but after converting the height difference becomes 0 or 1 for all of the nodes present in the BST.
Approach #1🧑💻
The very basic approach would be to traverse the given tree in inorder and while traversing keep on inserting the nodes into a self-balancing tree like an AVL tree or red-black tree.
In this article, we will be using AVL tree. To know more about insertion in AVL tree have a look at the below-mentioned blog.
Pseudocode
-
Start
-
Store the inorder traversal of our tree into an Array.
-
Traverse the array and keep on inserting the values one-by-one into a self-balancing AVL tree.
-
Exit
In the below implementation most of the code has been taken from this “Insertion in AVL Trees” article. To fully understand the code make sure you go through the above article first.
Implementation in C++ 🧑💻
#include <bits/stdc++.h>
// AVL Tree implementation
// To know more about it. Have a look at the article mentioned above.
#include "AVL_Tree.h"
using namespace std;
// Node
class Node
{
public:
int data;
Node *left, *right;
Node(int val)
{
data = val;
left = right = nullptr;
}
};
// generate an array from inorder traversal
void genArray(Node *root, vector<Node *> &arr)
{
if (root == nullptr)
return;
genArray(root->left, arr);
arr.push_back(root);
genArray(root->right, arr);
}
// preorder traversal
void preorder(Node *root)
{
if (root == nullptr)
return;
cout << root->data << " ";
preorder(root->left);
preorder(root->right);
}
// preorder traversal for AVL tree
void preOrderAVL(AVLtree *root)
{
if (root != NULL)
{
cout << root->data << " ";
preOrderAVL(root->left);
preOrderAVL(root->right);
}
}
int main()
{
/*
Creating BST
20
/ \
10 40
\
12
/
11
*/
Node *root = nullptr;
root = new Node(20);
root->left = new Node(10);
root->right = new Node(40);
root->left->right = new Node(12);
root->left->right->left = new Node(11);
cout << "Before Converting: ";
preorder(root);
// generating array from inorder traversal
vector<Node *> arr;
genArray(root, arr);
// traversing the array and inserting the values into
// self-balancing AVL tree one-by-one
AVLtree *tree = nullptr;
for (int i = 0; i < arr.size(); i++)
{
tree = insertNode(tree, arr[i]->data);
}
cout << "\n";
cout << "After converting: ";
preOrderAVL(tree);
cout << "\n";
return 0;
}
Output
Before Converting: 20 10 12 11 40
After converting: 11 10 20 12 40
Time Complexity ⌛
Insertion in AVL trees requires the same amount of time as a BST, which is O(h), where h is the tree's height. However, because our tree is equally balanced in height, the height is always O (log n). Considering all of these elements, the insert function's time complexity is determined to be O. (log n).
Thus, the overall time complexity (average and worst) of the insertion function in an AVL tree is O(log n).
The time required to generate the sorted array is O(N), as we are only doing the in-order traversal. Where N is the total number of nodes in our BST.
We are inserting N nodes into the AVL tree so the overall time complexity of our program is O(Nlog n).
Space Complexity 🚀
We are generating a new Array to store the nodes. So, the space complexity of our program would be O(N). Where N is the number of nodes in our BST.
27+ registered 
