public class BSTFromSortedArray {
Tree root;
static class Tree{
int data;
Tree left;
Tree right;
Tree(int data){
this.data = data;
this.left = this.right = null;
}
@Override
public String toString() {
return "Tree [data=" + data + ", left=" + left + ", right=" + right + "]";
}
}
void makeTree(int[] arr){
root = makeBST(arr, 0, arr.length-1);
}
// this methow is working like binary search on array creating each node each time.
Tree makeBST(int[] arr, int start, int end){
if(start>end){
return null;
}else{
int mid = (start+end)/2;
Tree node = new Tree(arr[mid]);
node.left = makeBST(arr, start, mid-1);
node.right = makeBST(arr, mid+1, end);
return node;
}
}
void printTreeInorder(Tree root){
if(root == null)return ;
else{
printTreeInorder(root.left);
System.out.print(root.data+" ");
printTreeInorder(root.right);
}
}
void printTreePreorder(Tree root){
if(root == null)return ;
else{
System.out.print(root.data+" ");
printTreePreorder(root.left);
printTreePreorder(root.right);
}
}
void printTreePostorder(Tree root){
if(root == null)return ;
else{
printTreePostorder(root.left);
printTreePostorder(root.right);
System.out.print(root.data+" ");
}
}
public static void main(String[] args) {
int[] arr = {1,2,3,4,5,6,7,8,9};
BSTFromSortedArray t = new BSTFromSortedArray();
t.makeTree(arr);
System.out.println("Inorder");
t.printTreeInorder(t.root);
System.out.println("\nPreorder");
t.printTreePreorder(t.root);
System.out.println("\nPostorder");
t.printTreePostorder(t.root);
}
}
Output :
Inorder
1 2 3 4 5 6 7 8 9
Preorder
5 2 1 3 4 7 6 8 9
Postorder
1 4 3 2 6 9 8 7 5