/************************************************************

    Following is the TreeNode class structure

    template <typename T>
    class TreeNode {
       public:
        T data;
        TreeNode<T> *left;
        TreeNode<T> *right;

        TreeNode(T data) {
            this->data = data;
            left = NULL;
            right = NULL;
        }
    };

************************************************************/

string serializeTree(TreeNode<int> *root)
{
 //    Write your code here for serializing the tree
queue<TreeNode<int>*> q;
    q.push(root);
    string output="";
    while(!q.empty()){
         TreeNode<int> *temp=q.front();
        q.pop();
     if(temp!=NULL) {
        char c=48+temp->data;
        output=output+c+" ";
        q.push(temp->left);
        q.push(temp->right);
       }
      else output=output+"-1 ";
    }
    return output;
}
TreeNode<int>* deserializeTree(string &serialized)
{
 //    Write your code here for deserializing the tre
    if(serialized[0]=='-') return NULL;
    queue<TreeNode<int>*>  q;
    int curr=serialized[0]-48;
    TreeNode<int> *root=new TreeNode<int>(curr);
    q.push(root);
    int i=2;
    while(!q.empty()){
        TreeNode<int> *top=q.front();
        q.pop();
        int val1=serialized[i]-48;
        if(val1>=0){
            TreeNode<int> *Node1=new TreeNode<int>(val1);
            q.push(Node1);
            top->left=Node1;
            i+=2;
        }
        else  i+=3;
        int val2=serialized[i]-48;
        if(val2>=0){
            TreeNode<int> *Node2=new TreeNode<int>(val2);
            q.push(Node2);
            top->right=Node2;
            i+=2;
        }
        else   i+=3;
    }
    return root;
}