# Serialize and Deserialize binary tree

class Codec {
public:
    
    // 1(2()())(3(4()())(5()()))
    
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (root == NULL) {
            return string("");
        }
        string num = to_string(root->val);
        return num + "(" + serialize(root->left) + ")(" + serialize(root->right) + ")"; 
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int nextStart = 0;
        return parse(data, 0, &nextStart);
    }
    
    TreeNode* parse(string& data, int cur, int* nextStart) {
        if (cur >= data.size()) {
            return NULL;
        }
        if (data[cur] == ')') {
            *nextStart = cur + 1;
            return NULL;
        }
        
        int numEnd = data.find_first_of("(", cur);
        int num = stoi(data.substr(cur, numEnd - cur));
        TreeNode* node = new TreeNode(num);
        node->left = parse(data, numEnd + 1, nextStart);
        node->right = parse(data, *nextStart + 1, nextStart);
        *nextStart += 1;
        return node;
    }
};