Given an unsorted array of integers which represents binary search tree keys, construct a height balanced BST from it.

We have already discussed how to insert a key in BST. The height of such BST in worst case can be as much as number of keys in BST. The worst case happens when given keys are sorted in ascending or descending order and we get a skewed tree where all the nodes except leaf have one and only one child.

For a height balanced BSTs, with each comparison we skip about half of the tree, so that each insertion operation takes time proportional to the logarithm of the number of items n stored in the tree i.e. log_{2}n. This is much better than the linear time required to find items by key in an (unsorted) array or unbalanced trees.

We can easily modify the solution to get height balanced BSTs if all keys are known in advance. The idea is to sort the given keys first. Then the root will be the middle element of the sorted array and we recursively construct the left subtree of root by keys less than the middle element and right subtree of root by keys more than the middle element.

For example,

Below is C++/Java implementation of the idea:

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 |
#include <iostream> #include <algorithm> using namespace std; // Data structure to store a Binary Search Tree node struct Node { int data; Node *left, *right; }; // Function to create a new binary tree node having given key Node* newNode(int key) { Node* node = new Node; node->data = key; node->left = node->right = nullptr; return node; } // Function to perform in-order traversal of the tree void inorder(Node* root) { if (root == nullptr) return; inorder(root->left); cout << root->data << " "; inorder(root->right); } // Recursive function to insert an key into BST Node* insert(Node* root, int key) { // if the root is null, create a new node an return it if (root == nullptr) return newNode(key); // if given key is less than the root node, recurse for left subtree if (key < root->data) root->left = insert(root->left, key); // if given key is more than the root node, recurse for right subtree else root->right = insert(root->right, key); return root; } // Function to construct balanced BST from given sorted array // Note - root of the tree is passed by reference here void convert(int keys[], int low, int high, Node* &root) { // base case if (low > high) return; // find middle element of current range int mid = (low + high) / 2; // construct a new node from mid element and assign it to root root = newNode(keys[mid]); // left subtree of root will be formed by keys less than mid element convert(keys, low, mid - 1, root->left); // right subtree of root will be formed by keys less than mid element convert(keys, mid + 1, high, root->right); } // Function to construct balanced BST from given unsorted array Node* convert(int keys[], int n) { // sort the keys first sort(keys, keys + n); // construct balanced BST Node *root = nullptr; convert(keys, 0, n-1, root); // return root node of the tree return root; } // Construct balanced BST from given keys int main() { // input keys int keys[] = { 15, 10, 20, 8, 12, 16, 25 }; int n = sizeof(keys)/sizeof(keys[0]); // construct balanced binary search tree Node* root = convert(keys, n); // print the keys in in-order fashion inorder(root); return 0; } |

`Output:`

8 10 12 15 16 20 25

## Java

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
import java.util.Arrays; // Data structure to store a Binary Search Tree node class Node { int data; Node left = null, right = null; Node(int data) { this.data = data; } } class BST { // Function to perform in-order traversal of the tree public static void inorder(Node root) { if (root == null) { return; } inorder(root.left); System.out.print(root.data + " "); inorder(root.right); } // Function to construct balanced BST from given sorted array public static Node convert(int[] keys, int low, int high, Node root) { // base case if (low > high) { return root; } // find middle element of current range int mid = (low + high) / 2; // construct a new node from mid element and assign it to root root = new Node(keys[mid]); // left subtree of root will be formed by keys less than mid element root.left = convert(keys, low, mid - 1, root.left); // right subtree of root will be formed by keys less than mid element root.right = convert(keys, mid + 1, high, root.right); return root; } // Function to construct balanced BST from given unsorted array public static Node convert(int[] keys) { // sort the keys first Arrays.sort(keys); // construct balanced BST and // return root node of the tree return convert(keys, 0, keys.length - 1, null); } // Construct balanced BST from given keys public static void main(String[] args) { // input keys int[] keys = { 15, 10, 20, 8, 12, 16, 25 }; // construct balanced binary search tree Node root = convert(keys); // print the keys in in-order fashion inorder(root); } } |

`Output: `

8 10 12 15 16 20 25

The time complexity of above solution is O(nlog(n)).

**Thanks for reading.**

Please use our online compiler to post code in comments. To contribute, get in touch with us.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply