Sort array to bst

By | January 31, 2015
Share the joy
  •  
  •  
  •  
  •  
  •  
  •  

The problem is from g4g. link
Problem: Given a sorted array. Write a function that creates a Balanced Binary Search Tree using array elements.
Basic idea is to create the tree by the middle position. Then recursively create the left sub tree and right sub tree by left part array and right part array.

  1. package feb;
  2. public class SortArrayToBST {
  3.     public static void main(String[] args) {
  4.         int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
  5.         Tree t = getBSTBySortedArray(arr);
  6.     }
  7.     public static Tree getBSTBySortedArray(int[] arr) {
  8.         if (arr == null) {
  9.             return null;
  10.         }
  11.         return getBSTBySortedArrayUtil(arr, 0, arr.length – 1);
  12.     }
  13.     public static Tree getBSTBySortedArrayUtil(int[] arr, int start, int end) {
  14.         if (start > end) {
  15.             return null;
  16.         }
  17.         if (start == end) {
  18.             return new Tree(arr[start]);
  19.         }
  20.         int mid = (start + end) >> 1;
  21.         Tree tree = new Tree(arr[mid]);
  22.         tree.left = getBSTBySortedArrayUtil(arr, start, mid – 1);
  23.         tree.right = getBSTBySortedArrayUtil(arr, mid + 1, end);
  24.         return tree;
  25.     }
  26.     static class Tree {
  27.         int value;
  28.         Tree left;
  29.         Tree right;
  30.         Tree(int value) {
  31.             this.value = value;
  32.         }
  33.     }
  34. }