SortedArrayToBST.java

/*
Convert Sorted Array to Binary Search Tree

You are given an array of integers arr[], where 
the elements of the array are sorted in ascending order, 
your task is to convert it to a height balenced binary 
search tree which is a binary tree in which the depth of 
the two subtrees of every node never differs by more than one.
*/

import java.io.*;
import java.util.Scanner;
import java.util.*;

//defining a class for storing nodes of tree
class BTNode 
{
    int value;
    BTNode left;
    BTNode right;
    BTNode() 
    {}
    BTNode(int value) 
    {
        this.value = value; 
    }
    BTNode(int value, BTNode left, BTNode right) 
    {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

public class SortedArrayToBST
{
    //function to convert the sorted array to BST
    public BTNode sortedArrtoBST(int[] arr)
    {
        //if the array is empty then simply return zero
        if(arr == null || arr.length == 0)
        {
            return null;
        }

        //otherwise recursively call the array and then construct the BST
        return constructBST(arr, 0, arr.length - 1);
    }

    //function to construct the BST
    public BTNode constructBST(int[] arr, int left, int right)
    {
        int lftprt = left;
        int rtprt = right;
        //if the left pointer is greater than right pointer 
        //then then simply return
        //this is a kind of check for sorted array
        if(lftprt > rtprt)
        {
            return null;
        }

        //otherwise we go for recursive call
        int mid = lftprt + (rtprt - lftprt) / 2;
        BTNode curr = new BTNode(arr[mid]);
        curr.lftprt = constructBST(arr, lftprt, mid - 1);
        curr.rtprt = constructBST(arr, mid + 1, rtprt);

        //returning the node generated
        return curr;
    }

    //drivers code 
    public static void main (String[] args) throws IOException
    {
        // Taking input
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        System.out.println("Enter the number of elements in array : ");
        int n = br.nextInt();

        int []arr = new int[n];
        System.out.println("Enter the array element in sorted order : ");
        for(int i = 0; i < n; i++)
        {
            arr[i] = br.nextInt();
        }

        //for output
        System.out.println("Binary search tree formed is : ");
        sortedArrtoBST(arr);

        //printing the tree order thus generated
        for(int i = 0; i < n; i++)
        {
           System.out.print(arr[i]);
        }

        System.out.println(" ");
    }
}

/*
EXAMPLES:-

INPUT--
Enter the number of elements in array : 5
Enter the array element in sorted order : -10 -3 0 5 9
OUTPUT--
Binary search tree formed is : 0 -3 9 -10 null 5
     0
    / \
   -3  9
   /   /
 -10   5
It can also be 0 -10 5 null -3 null 9
     0
    / \
  -10  5
    \   \
    -3   9

TIME COMPLEXITY -- > O(N), where N is the number of nodes
SPACE COMPLEXITY --> O(1)
*/