static class BST {
private class Node {
int data;
Node left;
Node right;
}
private Node root;
public BST(int[] arr) {
root = construct(arr, 0, arr.length - 1);// recursive call to make the tree with lo = 0 and high =
// arr.length-1
}
private Node construct(int[] arr, int lo, int hi) {
// base case
if (lo > hi) {
return null;
}
// mid
int mid = (lo + hi) / 2;// take mid node each time to create balanced tree
// create new node
Node nn = new Node();
nn.data = arr[mid];
nn.left = construct(arr, lo, mid - 1);// recursive call to create left subtree
nn.right = construct(arr, mid + 1, hi);// recursive call to create right subtree
return nn;
}
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 static void main(String[] args) {
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);
bst.preOrder();
}
}