import java.util.*;
public class Main {
static class Index {
int index = 0;
}
static class BST {
Index index = new Index();
private class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
this.left = this.right = null;
}
public Node() {
}
}
private Node root;
public BST(int[] arr) {
this.root = construct(arr, index, arr[0], Integer.MIN_VALUE, Integer.MAX_VALUE, arr.length);
}
private Node construct(int[] pre, Index preIndex, int key, int min, int max, int size) {
if (preIndex.index >= size) {
return null;
}
Node root = null;
if (key > min && key < max) {
root = new Node(key);
preIndex.index = preIndex.index + 1;
if (preIndex.index < size) {
root.left = construct(pre, preIndex, pre[preIndex.index], min, key, size);
}
if (preIndex.index < size) {
root.right = construct(pre, preIndex, pre[preIndex.index], key, max, size);
}
}
return root;
}
public void display() {
this.display(this.root);
}
private void display(Node node) {
// base case
if (node == null) {
return;
}
// self work
String str = "";
if (node.left == null) {
str += ".";
} else {
str += node.left.data;
}
str += " -> " + node.data + " <- ";
if (node.right == null) {
str += ".";
} else {
str += node.right.data;
}
System.out.println(str);
// left
display(node.left);
// right
display(node.right);
}
public boolean find(int item) {
return this.find(this.root, item);
}
private boolean find(Node node, int item) {
// base case
if (node == null) {
return false;
}
if (item > node.data) {// search in right tree
return find(node.right, item);
} else if (item < node.data) {// search in left tree
return find(node.left, item);
} else {// if item = data
return true;
}
}
public void add(int item) {
this.add(this.root, item);
}
private void add(Node node, int item) {
if (item > node.data) {// if item is greater add to right
if (node.right == null) {// if node doesnt has right then add here
Node nn = new Node();
nn.data = item;
node.right = nn;
} else {// if node has right child then it will handle where to place it
add(node.right, item);
}
} else {// if(item<=node.data
if (node.left == null) {
Node nn = new Node();
nn.data = item;
node.left = nn;
} else {
add(node.left, item);
}
}
}
public int max() {
return this.max(this.root);
}
private int max(Node node) {
if (node.right == null) {// if node doesn't have right child therefore it is maximum return its
return node.data;
} else {// else go to right
return max(node.right);
}
}
public void remove(int item) {
this.remove(this.root, null, false, item);// node,parent node,lchild or rchild,item, for root node parent is
// null and it doesnt make sense to call it left or right child
// of
// null therefore we can pass anyting
}
private void remove(Node node, Node parent, boolean ilc, int item) {
if (node == null) {// node is not present
return;
}
if (item > node.data) {// right call
remove(node.right, node, false, item);
} else if (item < node.data) {// left call
remove(node.left, node, true, item);
} else {
if (node.left == null && node.right == null) {// case 1
if (ilc) {// 1b
parent.left = null;
} else {// 1a
parent.right = null;
}
} else if (node.left == null && node.right != null) {// case 2
if (ilc) {// 2b
parent.left = node.right;
} else {// 2a
parent.right = node.right;
}
} else if (node.left != null && node.right == null) {// case 3
if (ilc) {// 3b
parent.left = node.left;
} else {// 3a
parent.right = node.left;
}
} else {// case 4
int max = max(node.left);
node.data = max;// replace with max
remove(node.left, node, true, max);// delete max
}
}
}
public void preOrder() {
this.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 inRange(int a, int b) {
inRange(this.root, a, b);
}
private void inRange(Node node, int a, int b) {
if (node == null) {
return;
}
inRange(node.left, a, b);
if (node.data >= a && node.data <= b) {
System.out.print(node.data + " ");
}
inRange(node.right, a, b);
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t-- != 0) {
int n = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
BST bst = new BST(a);
int k1 = sc.nextInt();
int k2 = sc.nextInt();
System.out.print("# Preorder : ");
bst.preOrder();
System.out.println();
System.out.print("# Nodes within range are : ");
bst.inRange(k1, k2);
System.out.println();
}
}
}