text: /*
  Problem Link: https://practice.geeksforgeeks.org/problems/serialize-and-deserialize-a-binary-tree/1
  Title: Serialize and Deserialize a Binary Tree
  Difficulty: Medium
  Author: Hariket Sukesh Kumar Sheth
  Language: C++
  */
  
  #include <bits/stdc++.h>
  
  using namespace std;
  
  // Tree Node
  struct Node {
      int data;
      Node *left;
      Node *right;
  
      Node(int val) {
          data = val;
          left = right = NULL;
      }
  };
  
  Node *buildTree(string str) {
      // Corner Case
      if (str.length() == 0 || str[0] == 'N')
          return NULL;
      vector<string> ip;
  
      istringstream iss(str);
      for (string str; iss >> str;)
          ip.push_back(str);
  
      Node *root = new Node(stoi(ip[0]));
  
      // Push the root to the queue
      queue<Node *> queue;
      queue.push(root);
  
      // Starting from the second element
      int i = 1;
      while (!queue.empty() && i < ip.size()) {
  
          // Get and remove the front of the queue
          Node *currNode = queue.front();
          queue.pop();
          string currVal = ip[i];
          if (currVal != "N") {
              currNode->left = new Node(stoi(currVal));
  
              // Push it to the queue
              queue.push(currNode->left);
          }
  
          // For the right child
          i++;
          if (i >= ip.size())
              break;
          currVal = ip[i];
  
          // If the right child is not null
          if (currVal != "N") {
  
              // Create the right child for the current Node
              currNode->right = new Node(stoi(currVal));
  
              // Push it to the queue
              queue.push(currNode->right);
          }
          i++;
      }
  
      return root;
  }
  
  
  class Solution
  {
      public:
      vector<int> serialize(Node *root) 
      {
          vector<int>v;
           if(root==NULL)
         {
             v.push_back(-1);
             return v;
         }
         serialize(root->left);
         cout<<root->data<<" ";
         serialize(root->right);
      }
    
     int i=0;
      Node * deSerialize(vector<int> &A)
      {
           if(A.size()==0) return NULL;
        if(A[i]==-1) 
        {
            i++;
            return NULL;
        }
        Node* root=new Node(A[i++]);
        root->left=deSerialize(A);
        root->right=deSerialize(A);
        return root;
      }
  
  };
  
  
  void inorder(Node *root) {
      if (root == NULL)
          return;
      inorder(root->left);
      cout << root->data << " ";
      inorder(root->right);
  }
  
  void _deleteTree(Node* node)  
  {  
      if (node == NULL) return;  
    
      _deleteTree(node->left);  
      _deleteTree(node->right);  
    
      delete node;  
  }  
  
  void deleteTree(Node** node_ref)  
  {  
      _deleteTree(*node_ref);  
      *node_ref = NULL;  
  }  
  
  int main() {
      int tc;
      scanf("%d ", &tc);
      while (tc--) {
          string treeString;
          getline(cin, treeString);
          Node *root = buildTree(treeString);
          
          Solution serial, deserial;
          vector<int> A = serial.serialize(root);
          deleteTree(&root);
          Node *getRoot = deserial.deSerialize(A);
          inorder(getRoot);
          cout << "\n";
  
      }
  
  
      return 0;
  }
  