dsa_level_traversals

#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;
}

node *addL(node *p, int x)
{
    node *temp = p;
    node *te1 = create(x);
    temp->l = te1;
    return temp;
}

node *addR(node *p, int x)
{
    node *temp = p;
    node *te1 = create(x);
    temp->r = te1;
    return temp;
}

void travel(node *root, int x, int y, char c)
{
    node *p = root;
    if(p->val == x)
    {
        if(c == 'L')
            p = addL(p, y);
        else
            p = addR(p, y);
    }
    if(p->l != NULL)
        travel(p->l, x, y, c);
    if(p->r != NULL)
        travel(p->r, x, y, c);
}

void pre(node *root)
{
    node *p = root;
    cout << p->val << " ";
    if(p->l != NULL)
        pre(p->l);
    if(p->r != NULL)
        pre(p->r);
}

void level(node *root)
{
    node *p = root;
    queue<node*> q;
    q.push(p);
    while(!q.empty())
    {
        cout << q.front()->val << " ";
        if(q.front()->l != NULL)
            q.push(q.front()->l);
        if(q.front()->r != NULL)
            q.push(q.front()->r);
        q.pop()
    }
}

void solve()
{
    int n;
    cin >> n;
    int a, b;
    char c;
    cin >> a >> b >> c;
    n--;
    node *root = create(a);
    node *te = root;
    travel(te, a, b, c);
    while(n--)
    {
        cin >> a >> b >> c;
        travel(te, a, b, c);
    }
    node *tem0 = root, *tem1 = root, *tem2 = root, *tem3 = root;
    level(tem0);
    cout << el;
//  in(tem1);
//  cout << el;
//  pre(tem2);
//  cout << el;
//  post(tem3);
//  cout << el;
}

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