Convert a normal BST to Balanced BST in C++

In this tutorial, we will be discussing a program to convert a normal binary search tree to balanced binary search tree.

For this we will be provided with a skewed binary search tree either left or right. Our task is to convert it into a balanced binary search tree following a certain set of rules.

Example

 Live Demo

#include <bits/stdc++.h> using namespace std; //node structure of tree struct Node{    int data;    Node* left, *right; }; //traversing tree and storing node pointers //in vector nodes void store_nodes(Node* root, vector<Node*> &nodes){    if (root==NULL)       return;    store_nodes(root->left, nodes);    nodes.push_back(root);    store_nodes(root->right, nodes); } //constructing binary tree Node* construct_tree(vector<Node*> &nodes, int start, int end){    if (start > end)       return NULL;    //make the middle element to be the root    int mid = (start + end)/2;    Node *root = nodes[mid];    root->left = construct_tree(nodes, start, mid-1);    root->right = construct_tree(nodes, mid+1, end);    return root; } //converting an unbalanced BST to a balanced BST Node* buildTree(Node* root){    //storing nodes of given BST in sorted order    vector<Node *> nodes;    store_nodes(root, nodes);    int n = nodes.size();    return construct_tree(nodes, 0, n-1); } //creation of new node Node* newNode(int data){    Node* node = new Node;    node->data = data;    node->left = node->right = NULL;    return (node); } //performing preorder traversal void preOrder(Node* node){    if (node == NULL)       return;    printf("%d ", node->data);    preOrder(node->left);    preOrder(node->right); } int main(){    Node* root = newNode(10);    root->left = newNode(8);    root->left->left = newNode(7);    root->left->left->left = newNode(6);    root->left->left->left->left = newNode(5);    root = buildTree(root);    printf("Preorder traversal of balanced BST : \n");    preOrder(root);    return 0; }

Output

Preorder traversal of balanced BST : 7 5 6 8 10