Zig-Zag bottom up level order

import java.io.*;
import java.util.*;
class Node{
    int data;
    Node left,right;
    Node(int data){
        this.data=data;
        left=right=null;
    }
}
public class Solution {
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
    static Queue<Node> q=new LinkedList<>();
    static void reversequeue(){
        Stack<Node> stack = new Stack<>();
        while (!q.isEmpty()) {
            stack.add(q.peek());
            q.remove();
        }
        while (!stack.isEmpty()) {
            q.add(stack.peek());
            stack.pop();
        }
    }
    static void zigZag(Node root)throws IOException{
        q.add(root);
        int i=1;
        Stack<Integer> st=new Stack<>();
        while(!q.isEmpty()){
            int x=q.size();
            if(i%2==0){
                while(x-->0){
                    Node temp=q.poll();
                    st.push(temp.data);
                    if(temp.right!=null)
                        q.add(temp.right);
                    if(temp.left!=null)
                        q.add(temp.left);
                }
            }
            else{
                reversequeue();
                while(x-->0){
                    Node temp=q.poll();
                    st.push(temp.data);
                    if(temp.left!=null)
                        q.add(temp.left);
                    if(temp.right!=null)
                        q.add(temp.right);
                }
                reversequeue();
            }
            i++;
        }
        while(st.size()>0){
            bw.write(st.peek()+" ");
            st.pop();
        }
    }
    static Node insert(Node root,int data){
        if(root==null)
            return new Node(data);
        else{
            Node curr;
            if(data<=root.data){
                curr=insert(root.left,data);
                root.left=curr;
            }
            else{
                curr=insert(root.right,data);
                root.right=curr;
            }
        }
        return root;
    }
    public static void main(String[] args) throws IOException{
        int t=Integer.parseInt(br.readLine());
        while(t-->0){
            int n=Integer.parseInt(br.readLine());
            String[] st=br.readLine().split(" ");
            Node root=null;
            for(int i=0;i<n;i++){
                root=insert(root,Integer.parseInt(st[i]));
            }
            if(root==null){
            bw.write("\n");
                t--;
                continue;
            }
            zigZag(root);
            bw.write("\n");
        }
        bw.flush();
    }
}