## How to build a Binary Search Tree from a sorted array in Java?

Write a program to build Binary Search Tree from a sorted array in Java. Print the output as preorder traversal of BST.

#### Posted by Nikheel on December 14th 2017 05:11 AM

Binary Search Tree (BST) : All the nodes of Binary Search Tree must follow following rules : 1. The left sub-tree of a node must have a key that is less than or equal to its parent node's key. 2. The right sub-tree of a node must have a key that is greater than to its parent node's key. Steps to build a BST from sorted array : 1. Find the middle element of an array and make it root. 2. Recursively do same thing for left subtree and right subtree. 2.1 Find the middle element of left subtree and make it left child of the root created in step 1. 2.2 Find the middle element of right sub tree and make it right child of the root created in step 1. Now let's take a look at the code. Here we will first find the root node from an array, by calculating middle index of an array. So we will have two sets of arrays, same procedure will be repeated until the end and smaller elements will be added to left sub-tree and larger ones will be added to right sub-tree. Once we get a BST we will print preorder of BST as an output

//Build BST from an array in Java

package collections;

//node of BST
class Node {

int data;

Node leftright;

Node(int d) {

data d;

left right null;
}
}

public class
BSTfromArray {

static
Node root;

//  method to construct Binary Search Tree
//first - first index of an array
//last - last index of an array

Node arrayToBST(int arr[], int firstint last) {

if (
first last) {
return
null;
}

// find middle element and make it root

int mid = (first last) / 2;

Node node = new Node(arr[mid]);

// construct the left subtree and make it left child of root

node.left arrayToBST(arrfirstmid 1);

//construct the right subtree and make it right child of root

node.right arrayToBST(arrmid 1last);

return
node;
}

// method to print preorder traversal of BST

void preOrder(Node node) {

if (
node == null) {
return;
}

System.out.print(node.data " ");

preOrder(node.left);

preOrder(node.right);
}

public static
void main(String[] args) {

BSTfromArray tree = new BSTfromArray();

//sorted array

int arr[] = new int[]{10123436394047};

int n arr.length;

root tree.arrayToBST(arr01);

System.out.println("Newly constructed BST : Preorder Traversal");

tree.preOrder(root);
}
} #### Posted by Nikheel on December 21st 2017 06:08 AM

Note : Java provides package system where we can store different classes under different packages to simplify project structure. Here we have used such a package, if any compile time error occurs try removing line that starts with "package".

• Minimum 20 character
3EBR