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,
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,
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.
Post a Comment