Cacher is the code snippet organizer for pro developers

// reconstruct_binary_tree_from_preorder
// idea: traverse sequence from right-to-left. push nodes and nulls on to a stack.
// everytime encounter a non-null node x, pop the stack twice: call the first popped l, the second r.
// then x->left = l, x->right = r.
// then, push x. when sequence is used up, a single node on stack will be left, which is the root.

// sequence: {2, 1, null, null, 3, null, null}
TreeNode* reconstruct_binary_tree_from_preorder(vector<string> &S) {
    if(S.empty()) return NULL;
    int N = S.size();
    stack<TreeNode*> stk;
    for(int i=N-1; i>=0; i--) {
        if(S[i] == "null") stk.push(NULL);
        else {
            TreeNode *root = new TreeNode(stoi(S[i]));
            TreeNode *l = stk.top();
            stk.pop();
            TreeNode *r = stk.top();
            stk.pop();
            root->left = l;
            roott->right = r;
            stk.push(root)
        }
    }
    return stk.top();
}

// reconstruct_binary_tree_from_postorder
// idea is similar to preorder, but we traverse from left-to-right. 
// when popping, stack top is the right child, and the node below is the right child.



// reconstruct_binary_tree_from_inorder
// IMPOSSIBLE! inorder sequence is insufficient to reconstruct a binary tree