How to build a Binary Search Tree from a sorted array in Java?
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
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".