Sorted Array to Balanced Binary Search Tree (BST)

Convert Sorted Array to Balanced Binary Search Tree

---

Given a sorted array, create a Balanced Binary Search Tree using array elements. A Binary Search Tree is called Balanced if, the height of left subtree and height of right subtree of Root differ by at most 1.

Lets understand the problem statement graphically and it will be more clear,

Algorithm

---

Solution to convert sorted Array to BST is very similar to Convert Sorted Linked list to BST 

We are given a sorted array, So which element we will pick as a Root Node for our BST such that it will be balanced. 
If we pick the middle element of the array as Root node and distribute the left portion of the array to Left subtree and right portion of array to Right subtree then it will be balanced.

So what we will do is,

1. Get the middle element of the array and make it as Root of Binary Search Tree.
    mid = [ start of array + ( end of array - start of array )/2 ] 

2. After getting the middle of array, it is divided into 2 parts, left half and right half.
    Middle element of Left half will become Left child of Root Node(created in step 1).
    Middle element of Right half will become Right child of Root Node(created in step 1).

    We can do above step recursively for left half and right half.
    a) Get the middle of left half and make it left child of the root created in step 1.
    b) Get the middle of right half and make it right child of the root created in step 1.

Recursive Stack trace will look like below,

Sorted Array to Binary Serach Tree Java Program

---

package javabypatel;

public class SortedArrayToBalancedBST {

 public static void main(String[] args) {
  new SortedArrayToBalancedBST();
 }

 public SortedArrayToBalancedBST(){
  int[] arr = new int[]{1,2};
  Node balancedBST = sortedArrayToBST(arr, 0, arr.length-1);
  printTreeInOrder(balancedBST);
 }

 private Node sortedArrayToBST(int[] arr, int start, int end){
  if(start>end){
   return null;
  }
  
  int mid = start + (end-start)/2;
  
  Node temp = new Node(arr[mid]);
  temp.setLeft(sortedArrayToBST(arr, start, mid-1));
  temp.setRight(sortedArrayToBST(arr, mid+1, end));
  
  return temp;
 }
 
 private void printTreeInOrder(Node rootNode){
  if(rootNode==null)
   return;
  printTreeInOrder(rootNode.getLeft());
  System.out.print(rootNode.getData() + " ");
  printTreeInOrder(rootNode.getRight());
 }
}

You may also like to see

---

Convert Sorted Linked List to balanced BST

Exception Handling Interview Question-Answer

Method Overloading - Method Hiding Interview Question-Answer

Advanced Multithreading Interview Questions-Answers In Java

Type Casting Interview Questions-Answers In Java

How Thread.join() in Java works internally

How is ambiguous overloaded method call resolved in java

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.