class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
      if (!root)
        return "";
      
      // Put the val first then append left and right subtree respectively
      string res = to_string(root->val);
      string left = serialize(root->left);
      if (!left.empty())
        res += " " + left;
      
      string right = serialize(root->right);
      if (!right.empty())
        res += " " + right;
      return res;
    }
  
    // Extract a number from a space delimited string
    string decompose(string data, int& num) {
      if (data.empty())
        return "";
      
      int empty_pos = data.find(" ");
      string num_str = data.substr(0, empty_pos);
      num = stoi(num_str);
      if (empty_pos == string::npos)
        return "";
      
      return data.substr(empty_pos + 1);
    }
  
    TreeNode* deserialize(vector<int>::iterator b, vector<int>::iterator e) {
      if (b == e)
        return nullptr;
      
      // First number is the root of the tree
      int root_val = *b;     
      auto root = new TreeNode(root_val);
      vector<int>::iterator it = b + 1;
      
      // Search for a larger number than the root which is the beginning of
      // the right subtree
      while (it != e && root_val >= *it)
        ++it;
      
      // Upto larger number is the left subtree
      root->left = deserialize(b + 1, it);
      
      // From the larger to the end is the right subtree
      root->right = deserialize(it, e);
      return root;
    }
  
    // First split the string into a vector and then deserialize the vector
    TreeNode* deserialize(string data) {
      vector<int> nums;
      int num;
      while (!data.empty()) {
        data = decompose(data, num);
        nums.push_back(num);     
      }
      
      return deserialize(begin(nums), end(nums));
    }
};