Prime Naukri

Construct BST

Send Feedback

Given a sorted integer array A of size n which contains all unique elements. You need to construct a balanced BST from this input array. Return the root of constructed BST.

Note : If array size is even, take first mid as root.

Input format :

Line 1 : Integer n (Size of array)
Line 2 : Array elements (separated by space)

Output Format :

BST elements (in pre order traversal, separated by space)

Sample Input :

7
1 2 3 4 5 6 7

Sample Output :

4 2 1 3 6 5 7 

2. public class Solution {
3. 
   
4. /* Binary Tree Node class 
5.  * 
6.  * class BinaryTreeNode<T> {
7. T data;
8. BinaryTreeNode<T> left;
9. BinaryTreeNode<T> right;
11. public BinaryTreeNode(T data) {
12. this.data = data;
13. }
14. }
15. */
16.     
17.     private static BinaryTreeNode<Integer> makeBstFromSortedArray(int[] arr,int start, int end) {
19. if(start>end)
20. {
21. return null;
22. }
25. int mid = (start+end)/2;
27. BinaryTreeNode<Integer> root = new BinaryTreeNode<>(arr[mid]);
29. //Now we will make left side of Bst
31. BinaryTreeNode<Integer> left = makeBstFromSortedArray(arr,start,mid-1);
33. //Now we will make right sider of binary search tree 
35. BinaryTreeNode<Integer> right = makeBstFromSortedArray(arr,mid+1,end);
37. root.left = left;
38. root.right = right;
39. return root;
43. }
44. 
    
45. public static BinaryTreeNode<Integer> SortedArrayToBST(int[] arr){
46.         
47.         int start = 0;
48. int end = arr.length-1;
50. return makeBstFromSortedArray(arr,start,end);
52. }
53. }