balanced_BST

#include <bits/stdc++.h>

#define ll long long
#define el endl
#define umi unordered_map<int, int>
#define umll unordered_map<ll, ll>
#define all(vect) vect.begin(), vect.end()
#define reset(A) memset(A, 0, sizeof(A))

const int mod = 1e9 + 7;

using namespace std;

struct node
{
    int val;
    node *l, *r;
};

node *create(int x)
{
    node *p = new node;
    p->val = x;
    p->l = NULL;
    p->r = NULL;
    return p;
}

node * insert(node * root, int x){
    node *p = root;
    if(p == NULL)
    {
        node * temp = create(x);
        return temp;
    }
    else
    {
        if(x < p -> val)
            p -> l = insert(p -> l, x);
        else
            p -> r = insert(p -> r, x);
    }
    return p;
}

int pre(node *root)
{
    int res = 0;
    node *p = root;
    if(p->l == NULL && p->r == NULL)
        res++;
    cout <<  p->val << " ";
    if(p->l != NULL)
    {
        res += pre(p->l);
    }
    if(p->r != NULL)
    {
        res += pre(p->r);
    }
    return res;
}

node *build(node *root, int a[], int st, int en)
{
    if(st > en)
        return;
    node *p = root;
    int r = (en - st) / 2;
    if(p->l == NULL && p->r == NULL)
        p = insert(p, a[r]);
    p->l = (p, a, st, r - 1);
    p->r = (p, a, r + 1, en);
}

void solve()
{
    int n;
    cin >> n;
    int a[n];
    for(int i = 0; i < n; i++)
        cin >> a[i];
    sort(a, a + n);

    node *root = new node;
    node *te = root;
    te = build(te, a, 0, n - 1);
    node *tem0 = root;
    int res = pre(tem0);
    cout << el << res;
    cout << el;
}

int main()
{
    int t = 1;
    cin >> t;
    while(t--)
    {
        solve();
    }
    return 0;
}