Binary Search Trees: Convert a normal BST into a Balanced BST

 Problem Statement:

You are given a BST root node, you need to make it as a balanced BST.

Example

Input:
       3
      /
     2
    /
   1

Output:
     2
   /   \
  1     3

Solution

The solution is simple. We follow below steps:

1. Get the nodes of BST in in-order traversal and store the result int he array. We know that in-order traversal will give the result in sorted order.

2. Get the middle of the array and make it as root.

3. Recursively perform the above step for left and right half.

 

Solution in C++

#include<iostream>
#include<vector>
#include<string>
#include<set>

using namespace std;


struct Node
{
    int data;
    struct Node *left, *right;
};

Node *get_new_node(int item)
{
    Node *temp =  new Node;
    temp->data = item;
    temp->left = temp->right = NULL;
    return temp;
}
 
Node* insert_into_bst(Node* node, int data) 
{ 
    if (node == NULL) return get_new_node(data); 
  
    if (data < node->data) 
        node->left  = insert_into_bst(node->left, data); 
    else if (data > node->data) 
        node->right = insert_into_bst(node->right, data);    
  
    return node; 
} 

void print_inorder(Node* Node) 
{ 
    if (Node == NULL) 
        return; 
    print_inorder(Node->left); 
    cout<<" "<<Node->data; 
    print_inorder(Node->right); 
} 
  
void store_inorder(Node* root, vector<struct Node*> &nodes)
{
    // base case
    if (root == nullptr) {
        return;
    }
 
    store_inorder(root->left, nodes);
    nodes.push_back(root); 
    store_inorder(root->right, nodes);
}


Node* build_tree(vector<struct Node*> &nodes, int start, int end) 
{ 
    // base case 
    if (start > end) 
        return NULL; 
  
    int mid = (start + end)/2; 
    Node *root = nodes[mid]; 

    root->left  = build_tree(nodes, start, mid-1); 
    root->right = build_tree(nodes, mid+1, end); 
  
    return root; 
} 


int main()
{
    Node *root = NULL; 
    root = insert_into_bst(root, 1); 
    insert_into_bst(root, 2); 
    insert_into_bst(root, 3); 
    insert_into_bst(root, 4); 
    insert_into_bst(root, 5); 

    vector<Node*> nodes; 
    store_inorder(root, nodes); 

    int n = nodes.size(); 

    root = build_tree(nodes, 0, n-1); 

    cout<<"Inorder order Traversal of tree"<<endl;
    print_inorder(root);

    return 0;
}

Output:

Inorder order Traversal of tree
1 2 3 4 5






Write a Comment

Leave a Comment

Your email address will not be published. Required fields are marked *