how we will construct BST if elements are given in unsorted order as video shows creation of BST in sorted order in unsorted order following a approach of finding mid element first will not give us BST
Construction of BST
@dheerajmishra992,
If elements are given in a random order and you need to construct a tree from that, you can sort the elements before construction.
Or if you are given the elements in say for example PreOrder traversal then you need to follow a different approach.
For PreOrder traversals:
The first element of preorder traversal is always root. We first construct the root.
Then we find the index of first element which is greater than root. Let the index be ‘i’. The values between root and ‘i’ will be part of left subtree, and the values between ‘i+1’ and ‘n-1’ will be part of right subtree.
Divide given preOrder of elements at index “i” and recur for left and right sub-trees.
Similarly you can think of an approach if elements are given in a Level Order traversal as well.
https://ide.codingblocks.com/s/231469 you can also refer to this code for unsorted arrays. When elements are given in a random order.
public class Main {
class Node{
int data;
Node left;
Node right;
Node(int data)
{
this.data=data;
}
}
public void Construct(int arr[],int low,int high){
if(low>high)
return null;
Node nn=new Node(arr[low]);
for(int i=low;i<=high;i++){
if(arr[i]>nn.data){
break;
}
nn.left=(arr,low+1,i-1);
nn.right=(arr,i,high);
return nn;
}
public void inorder(Node node){
if(node==null)
return null;
inorder(node.left);
System.out.println(node.data);
inorder(node.right);
}
public static void main(String args[]) {
Main mm=new Main();
int arr[]={15,10,8,12,20,16,25};
Node root=mm.Construct(arr,0,arr.length-1);
mm.inorder(root);
}
}**please tell me what’s wrong with this code I am getting errors in this **
this code is of constructing best from preorder traversal
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.