Untitled

import java.io.*;
import java.util.*;

class Node{
        Node left,right;
        int data;

        Node(int data){
            this.data = data;
            left = null;
            right = null;
        }
}

public class Solution { 

    public static Node insert(Node root, int data){
        if(root == null){
            
            return new Node(data);
        }
        if(root.data > data){
            root.left = insert(root.left, data);
        }
        else{
            root.right = insert(root.right, data);
        }
        
        return root;
    }

    public static void Preorder(Node root){
        if(root == null){
            return;
        }
        System.out.print(root.data+" ");
        Preorder(root.left);   
        Preorder(root.right);
    }

    public static void Inorder(Node root){
        if(root == null){
            return;
        }
        Inorder(root.left);
        System.out.print(root.data+" ");
        Inorder(root.right);
    }

    public static void Postorder(Node root){
        if(root == null){
            return;
        }
        Postorder(root.left);   
        Postorder(root.right);
        System.out.print(root.data+" ");
    }



    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner s = new Scanner(System.in);
        int t = s.nextInt();
        
        for(int x=0;x<t;x++){
            Node root = null;
            int n = s.nextInt();
            for(int i=0;i<n;i++){
                int data = s.nextInt();
                root = insert(root, data);
            }
            
            Preorder(root);
            System.out.println();
            Inorder(root);
            System.out.println();
            Postorder(root);
            System.out.println();
            
            System.out.println();
            
        }
    }
    
}