construct BST using preorder traversal.
At first I thought this was the same as serialization/deserialization of a generic BT. Since the problem suggests minimal codec size and avoid using any externa
At first I thought this was the same as serialization/deserialization of a generic BT. Since the problem suggests minimal codec size and avoid using any external variable/function/etc I chose preorder and using stack to avoid using aux function. It can be made a little easier if using recursion I suppose. Also I think postorder works as well.\n\n\n\n    class Codec {\n    public:\n    \n    \t// Encodes a tree to a single string.\n    \tstring serialize(TreeNode* root) {\n    \t\t// preorder traversal\n    \t\tstring ret;\n    \t\tif(!root) return ret;\n    \t\t\n    \t\tstack<TreeNode*> stk;\n    \t\tstk.push(root);\n    \t\twhile(!stk.empty()){\n    \t\t\tTreeNode *r = stk.top();\n    \t\t\tstk.pop();\n    \t\t\tret += to_string(r->val) + ",";\n    \t\t\tif(r->right) stk.push(r->right);\n    \t\t\tif(r->left) stk.push(r->left);\n    \n    \t\t}\n    \t\treturn ret.substr(0, ret.size()-1);\n    \t}\n    \n    \t// Decodes your encoded data to tre.\n    \tTreeNode* deserialize(string data) {\n    \t    if(data.size() == 0) return nullptr;\n    \t    \n    \t\tint id = 0;\n    \t\t// take root at first\n    \t\tint r = id;\n    \t\twhile(isdigit(data[r])) r++;\n    \t\tint v = stoi(data.substr(id, r-id));\n    \t\tid = r+1;\n    \n    \t\tTreeNode *root = new TreeNode(v);\n    \t\tstack<TreeNode*> stk;\n    \t\tstk.push(root);\n    \n    \t\twhile(id < (int) data.size()) {\n    \t\t\tint r = id;\n    \t\t\twhile(isdigit(data[r]))\tr++;\n    \t\t\tint v = stoi(data.substr(id, r - id));\n    \t\t\tid = r + 1;\n    \n    \t\t\tTreeNode *node = nullptr;\n    \t\t\twhile(!stk.empty() && v > stk.top()->val) {\n    \t\t\t\tnode = stk.top();\n    \t\t\t\tstk.pop();\n    \t\t\t}\n    \t\t\tif(node) {\n    \t\t\t\tnode->right = new TreeNode(v);\n    \t\t\t\tstk.push(node->right);\n    \t\t\t} else {\n    \t\t\t\tstk.top()->left = new TreeNode(v);\n    \t\t\t\tstk.push(stk.top()->left);\n    \t\t\t}\n    \t\t}\n    \n    \t\treturn root;\n    \t}\n    \t// for debug\n    \tvoid f(TreeNode *root) {\n    \t\tif(!root) return;\n    \t\tf(root->left);\n    \t\tcout << root->val << ", ";\n    \t\tf(root->right);\n    \t}\n    };
[]