Share & learn

Through Innovative Digital Library

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.
 



Answers

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".

Answer Question

Your email address will not be published. Required fields are marked *

  • Minimum 20 character
3EBR

related questions

Most liked questions

Most answered questions

Login
3EBR Refresh
Register
3EBR Refresh
Forgot password
Ask a Question
Minimum 20 character
Minimum 20 character
Reply
Minimum 20 character
3EBR Refresh