Balance a Binary Search Tree

There are many ways to balance out Binary Search Tree a.k.a. BST, but here we are going to create new balanced Binary Search tree from the given BST.

Let’s Discuss step by step

1. Traverse BST using Inorder traversal.

If you are familiar with Inorder traversal, you may know it traverses the tree by ascending order of node values.

Refer my post for more information on Inorder Traversal.

Here, We are going to perform the same operation on BST and store the result in Array, which would be a sorted array.

2. Traverse a sorted array using two pointers.

Here, we are going to use two pointers start and end to find mid, given by the formula,

mid = (start + end) /2

Use mid as an index to retrieve the value from the sorted array.

3. Create a new node.

We are going to create a new node with a value given by a sorted array using mid as an index.

This new node is our root node, having a middle value of the sorted sequence.

4. Create left and right subtree for Balanced BST

This one we are going to achieve using recursion. So go back to Step 2 and perform the same operation for the left and right subtree.

5. Return new node

Few things to remember, if you are familiar with binary search u may have noticed, we are using the same technique to traverse the sorted array. we’re updating start or end at each instance to get the desired value of mid.

For the complete code refer to this.

Thank you for reading this article, and I hope you enjoyed it.