Balance Binary Search Tree

To balance a binary search tree do

1. Get the in-order traversal of the given binary search tree.
2. Using the in-order traversal recursively create the balanced binary search tree.

Program to balance a binary search tree.

``````#include <iostream>
#include <vector>

using namespace std;

class Node {

public:

int val;
Node *left;
Node *right;

Node() : val(0), left(nullptr), right(nullptr) { }
Node(int x) : val(x), left(nullptr), right(nullptr) { }
Node(int x, Node *left_, Node *right_) : val(x), left(left_), right(right_) { }
};

class Tree {

public:

vector<int> vec_inorder;

Node* Construct (int start, int end) {

if (start > end) {
return nullptr;
}

int mid = start + (end - start) / 2;
Node * root = new Node (vec_inorder[mid]);
root->left = Construct (start, mid - 1);
root->right = Construct (mid + 1, end);
return root;
}

Node* BalanceBST (Node* root) {
InOrder (root);
return Construct (0, vec_inorder.size()-1);
}

void InOrder (Node* node) {
if (node != nullptr) {
InOrder (node->left);
vec_inorder.push_back(node->val);
InOrder (node->right);
}
}

void PreOrder (Node* node) {
if (node != nullptr) {
cout << node->val << " ";
PreOrder (node->left);
PreOrder (node->right);
}
}
};

int main () {
/* 1
\
2
\
3
\
4 */

Node node_4(4);
Node node_3(3, nullptr, &node_4);
Node node_2(2, nullptr, &node_3);
Node root_1(1, nullptr, &node_2);

Tree t;
Node * balanced_root = t.BalanceBST(&root_1);
/*     2
/ \
1   3
\
4 */
cout << "PreOrder traversal of balanced BST : ";
t.PreOrder(balanced_root);
return 0;
}
``````

Output

``````PreOrder traversal of balanced BST : 2 1 3 4
``````