/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:
    int finddepth(TreeNode* root){  //need to learn recurssion for finddepth
        if(!root){
            return 0;
        }
        else return max(1+finddepth(root->left),1+finddepth(root->right));
    }

    
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        int maxdepth=finddepth(root);
        int maxnumber=pow(2,maxdepth)-1;        //find max element number
        string str=string();   
        queue<TreeNode*> q;
        q.push(root);
        int visited=1;
        //use BFS to put store element in str
        while(q.size()>0){
            if(q.front()==NULL){
                str=str+"null,";
            }
            else{
                str=str+to_string(q.front()->val)+",";
            }
            
            if (visited < maxnumber) {//check whether put in redundant element
                if (q.front() != NULL) {
                    q.push(q.front()->left);
                    q.push(q.front()->right);
                    visited += 2;
                }
                else {
                    q.push(NULL);
                    q.push(NULL);
                    visited += 2;
                }
            q.pop();
            
        }

        cout<<str<<endl;
        return str;
    }

      TreeNode get(string s){
            if(s=="null"){
                return NULL;
            }
            else {
                int a=0;
                stringstream x;     //convert string to int
                x<<s;
                x>>a;
                return TreeNode(a);
            } 
         }

    // Decodes your encoded data to tree.
    vector<TreeNode> TN;
    TreeNode* deserialize(string data) {
          int lp=0,rp=0;
        while(rp<data.size()){
            rp=data.find(",",rp+1);
            TN.push_back(get(data.substr(lp,rp-lp)) );
            lp=rp+1;
        }

        int index=0;
        int pchild=1;

        while(pchild<TN.size()-1){
            TN.at(index).left=&TN.at(pchild++);
            TN.at(index).right=&TN.at(pchild++);
            index++;
            pchild++;
            
        } 
      
       return &TN[0];
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));