Mirror_tree.cpp

    using namespace std;
    #include <bits/stdc++.h>
    #define trace(x) cout<<#x<<": "<<x<<" ";
     
     
     
     
    typedef struct node
    {
    	int data;
    	struct node* left, *right;
    }
    Node;
     
    Node* NewNode(int x)
    {
    	Node* nn = new Node;
    	nn->data = x;
    	nn->left = nn->right = NULL;
     
    	return nn;
    }
     
    void inorder(Node* root)
    {
    	if(root == NULL)
    		return;
    	inorder(root->left);
    	cout<<root->data<<" ";
    	inorder(root->right);
    }
     
     
     
     
     
     
    int main(int argc, char const *argv[])
    {
    	ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
     
    	int t;
    	cin>>t;
    	while(t--)
    	{
    		int n;
    		cin>>n;
    		vector<int> a;
    		a.push_back(-1);
    		for (int i = 1; i <= n; i++) 
    		{
    			int x;
    			cin>>x;
    			a.push_back(x);
    		}
     
    		queue<pair<int, int> > qu;
    		qu.push(make_pair(0, 1));
     
    		map<int, int> lmp;
    		map<int, int> rmp;
     
    		while(!qu.empty())
    		{
    			int hd = qu.front().first;
    			int ind = qu.front().second;
    			
    			qu.pop();
     
    			if(lmp.find(hd) == lmp.end())
    				lmp[hd] = ind;
     
    			rmp[hd] = ind;
     
    			if((2*ind)>n)
    				continue;
     
    			if(a[2*ind] != 0)
    			{
    				qu.push(make_pair(hd+1, 2*ind));
    			}
     
    			if((2*ind+1)>n)
    				continue;
     
    			if(a[2*ind+1] != 0)
    			{
    				qu.push(make_pair(hd+1, 2*ind+1));
    			}
    		}
     
    		unordered_map<int, int> umap;
     
    		for(auto it = rmp.begin(); it!=rmp.end(); it++)
    		{
    			int x = a[(*it).second];
    			umap[(*it).second]++;
    			cout<<x<<endl;
    		}
     
    		for(auto it1 = lmp.begin(); it1 !=lmp.end(); it1 ++)
    		{
    			int d2 = a[(*it1).second];
     
    			if(umap[(*it1).second] == 0)
    				cout<<d2<<endl;
    		}
     
    		cout<<endl;
     
    	}
    	return 0;
    }