Recently I asked the doubt that BST input method taught is not working.Here is my code:
import java.util.Scanner;
import java.util.Arrays;
public class Main {
static Scanner scn = new Scanner(System.in);
public static void main(String args[]) {
int t = scn.nextInt();
Main m = new Main();
while(t–>0){
int n = scn.nextInt();
int[] arr = new int[n];
for(int i=0;i<n;i++)
arr[i] = scn.nextInt();
Arrays.sort(arr);
BinarySearchTree tree = m.new BinarySearchTree(arr);
tree.preorder();
System.out.println();
tree.find();
}
}
class BinarySearchTree{
private class Node{
int data;
Node left;
Node right;
}
private Node root;
BinarySearchTree(int[] arr){
this.root=takeinput(arr,0,arr.length-1);
}
private Node takeinput(int[] arr,int lo,int hi){
if(lo>hi){
return null;
}
int mid=(lo+hi)/2;
Node nn = new Node();
nn.data = arr[mid];
nn.left=takeinput(arr,lo,mid-1);
nn.right=takeinput(arr,mid+1,hi);
return nn;
}
public void preorder(){
preorder(this.root);
}
private void preorder(Node node){
if(node==null){
return;
}
System.out.print(node.data+" “);
preorder(node.left);
preorder(node.right);
}
public void find(){
int k1 = scn.nextInt();
int k2 = scn.nextInt();
find(this.root,k1,k2);
}
private void find(Node node,int lo,int hi){
if(node==null){
return ;
}
if(lo>node.data){
find(node.right,lo,hi);
}else if(hi<node.data){
find(node.left,lo,hi);
}else{
find(node.left,lo,hi);
System.out.print(node.data+” “);
find(node.right,lo,hi);
}
}
public void display(){
display(this.root);
}
private void display(Node node){
if(node==null){
return;
}
String str=”";
if(node.left!=null){
str+=node.left.data;
}else{
str+=“END”;
}
str+="=>"+node.data+"<=";
if(node.right!=null){
str+=node.right.data;
}else{
str+=“END”;
}
System.out.println(str);
display(node.left);
display(node.right);
}
}
}
The code I wrote
Don’t sort the array before construction. See you are given the elements of the tree are given to you in a preorder traversal. So you need to make a tree from that preOrder traversal.
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.
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.