Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Create a minimum height BST from a sorted array
import java.util.*;
public class MakeBSTFromArray {
public static void main(String[] args) {
int[] arr = {0,1,2,3};
Node root = makeBSTShorter(arr, 0, arr.length-1);
System.out.println("Level order: ");
root.printLevelOrderTree(root);
System.out.println("Pre order: ");
root.printPreorderTree(root);
}
public static Node makeBSTShorter(int[] arr, int start, int end) {
if (end < start) return null;
int mid = (start+end) / 2;
Node n = new Node(arr[mid]);
n.left = makeBSTShorter(arr, start, mid-1);
n.right = makeBSTShorter(arr, mid+1, end);
return n;
}
public static Node makeBST(int[] arr) {
// base case 0 - 1 element in array
if (arr.length == 1) {
System.out.println("ARRAY IS: "+Arrays.toString(arr));
return new Node(arr[0]);
}
// base case 1 - 2 elements in array
// make largest element root, smallest left subtree
if (arr.length == 2) {
Node n = new Node(arr[1]);
n.left = new Node(arr[0]);
return n;
}
// split array into 3 parts
// 1. left subtree
// 2. root (middle)
// 3. right subtree
int size = arr.length;
int mid = size / 2;
Node root = new Node(arr[mid]);
int[] leftSubTree = new int[mid];
int[] rightSubTree = new int[size - mid-1];
for (int i = 0; i < mid; i++) {
leftSubTree[i] = arr[i];
}
for (int j = mid+1; j < size; j++) {
rightSubTree[j-mid-1] = arr[j];
}
root.left = makeBST(leftSubTree);
root.right = makeBST(rightSubTree);
return root;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.