Test cases wrong. Getting correct for given example in question

#1

import java.util.*;
public class Main {

private class Node{
	int data;
	Node left;
	Node right;

	Node(int data, Node left, Node right){
		this.data=data;
		this.left=left;
		this.right=right;
	}
}
private Node root;

public Main(int[] arr){
	this.root= constructBST(arr,0,arr.length-1);
}

private Node constructBST(int arr[], int low, int high){

	if(low>high){
		return null;
	}

	int mid=(low+high)/2;
	Node node= new Node(arr[mid],null,null);

	node.left= constructBST(arr,low,mid-1);
	node.right=constructBST(arr,mid+1, high);

	return node;
}

public void PreOrder(){
	this.PreOrder_Traversal(this.root);
}

private void PreOrder_Traversal(Node node){
	
	if(node==null){
		return;
	}

	System.out.print(node.data+" ");
	PreOrder_Traversal(node.left);
	PreOrder_Traversal(node.right);
}



public static void main(String args[]) {

	Scanner sc= new Scanner(System.in);
	int tests= sc.nextInt();
	for(int test=0; test<tests; test++){

		int size=sc.nextInt();
		int arr[]= new int[size];
		for(int i=0; i<size; i++){
			arr[i]=sc.nextInt();
		}
		int k1=sc.nextInt();
		int k2=sc.nextInt();
		
		Arrays.sort(arr);

		Main tree= new Main(arr);
		System.out.print("# Preorder : ");
		tree.PreOrder();
		System.out.println();
		System.out.print("# Nodes within range are : ");
		for(int a:arr){
			if(a>=k1 && a<=k2){
				System.out.print(a+" ");
			}
		}



	}

}

}

#2

Hey @ANUKUL1509,
Your code is unable to generate the expected tree.

For the testcase,
1
5
4 3 2 5 6
3 5

The expected preorder of the tree is: 4 3 2 5 6
But your code is providing it as 4 2 3 5 6

To resolve this, try making inserting the nodes into the tree one by one rather than generating the tree using the sorted inorder property.

Also, for printing the numbers in the given range, you can perform an inorder traversal and print the value of all the nodes in the valid range.

#3

Hi Mihir. Changed the code according to your suggestion. Constructing the tree by adding nodes from the array. Getting correct answer for the example now. But still wrong for the test case.

#4

Try using the inorder traversal for printing the nodes rather than using the array.
And please share the updated code with me (use the online IDE).

#5

import java.util.*;
public class Main {

private class Node{
	int data;
	Node left;
	Node right;

	Node(int data, Node left, Node right){
		this.data=data;
		this.left=left;
		this.right=right;
	}
}
private Node root;

public Main(int[] arr){
	for(int i=0; i<arr.length; i++){
		addNode(arr[i]);
	}
}

public void addNode(int item){
	this.addNode(this.root,item);
}

private void addNode(Node node, int item){
	if(this.root==null){
		this.root= new Node(item,null,null);
	}else{
		if(item<node.data){
			if(node.left==null){
				node.left=new Node(item,null,null);
				return;
			}
			addNode(node.left,item);
		}else{
			if(node.right==null){
				node.right=new Node(item,null,null);
				return;
			}
			addNode(node.right,item);
		}
	}
}

public void PreOrder(){
	this.PreOrder_Traversal(this.root);
}

private void PreOrder_Traversal(Node node){
	
	if(node==null){
		return;
	}

	System.out.print(node.data+" ");
	PreOrder_Traversal(node.left);
	PreOrder_Traversal(node.right);
}

public ArrayList<Integer> InOrder(){
	return this.Inorder_Traversal(this.root);
}

private ArrayList<Integer> Inorder_Traversal(Node node){
	if(node==null){
		return new ArrayList<Integer>();
	}

	ArrayList<Integer> ans= new ArrayList<Integer>();
	ArrayList<Integer> leftList= Inorder_Traversal(node.left);

	for(int l: leftList){
		ans.add(l);
	}

	ans.add(node.data);

	ArrayList<Integer> rightList= Inorder_Traversal(node.right);

	for(int r: rightList){
		ans.add(r);
	}
	return ans;
}



public static void main(String args[]) {

	Scanner sc= new Scanner(System.in);
	int tests= sc.nextInt();
	for(int test=0; test<tests; test++){

		int size=sc.nextInt();
		int arr[]= new int[size];
		for(int i=0; i<size; i++){
			arr[i]=sc.nextInt();
		}
		int k1=sc.nextInt();
		int k2=sc.nextInt();

		Main tree= new Main(arr);
		System.out.print("# Preorder : ");
		tree.PreOrder();
		System.out.println();
		System.out.print("# Nodes within range are : ");
		
		ArrayList<Integer> inorderList= tree.InOrder();
		for(int item: inorderList){
			if(item>=k1 && item<=k2){
				System.out.print(item+" ");
			}
		}



	}

}

}

#6

Hey @ANUKUL1509,
You missed out printing a newline after every test case, thus your code wasn’t being accepted.

Apart from that you can optimise your solution by adding only those values to the arraylist during inorder traversal which lie in the range of k1 and k2.
while doing the inorder traversal the following 3 cases are possible:

if(node.data<k1){ 
        // answer won't lie in the left side of current node as all the values will be smaller 
        // but there might be a possible result in the right subtree
        
        Inorder_Traversal(node.right,k1,k2,ans);

    }else if(node.data>k2){
        // answer won't lie in the right side of current node as all the values will be larger 
        // but there might be a possible result in the left subtree

        Inorder_Traversal(node.left,k1,k2,ans);

    }else{
        // node lies in the range of k1 and k2 so simply do inorder traversal

        Inorder_Traversal(node.left,k1,k2,ans);
        ans.add(node.data);
        Inorder_Traversal(node.right,k1,k2,ans);
    }

You can perform the operations wisely to save extra memory being consumed.
I updated your code and optimised it a bit to save it from the extra memory being consumed.

You can refer to it here after trying to code it on your own:

Hope it helps :slight_smile:

#7

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.