TreeNode<char>* treeStringHelper(std::string& s, int height, int currentIndexTree,int& currentIndexString) {
    if (currentIndexTree <= 0 || currentIndexTree > height) {
        return nullptr;
    }

    if (height == currentIndexTree) {
        if (currentIndexString < s.size()) {
            currentIndexString++;
            return new TreeNode<char>(s[currentIndexString - 1]);
        }
        return nullptr;
    }
    else {
        TreeNode<char>* result = new TreeNode<char>(' ');

        result->left = treeStringHelper(s, height,currentIndexTree + 1, currentIndexString);
        result->right = treeStringHelper(s, height,currentIndexTree + 1, currentIndexString);

        return result;
    }
}

TreeNode<char>* treeString(std::string s) {
    size_t length = s.size();
    int height = 1;
    int lastLeavesLength = 1;
    while (lastLeavesLength < length) {
        height++;
        lastLeavesLength *= 2;
    }
    int index = 0;
    return treeStringHelper(s, height, 1, index);
}