Range invariant

The invariant is that each node will represent a range of valid values. For a binary tree, one end is unbounded. As you go down you partition ranges.

Is Valid BST

bool isValidBST(TreeNode* root) {
    const long long inf = 1e18;
    auto f = [&](auto&& f, TreeNode* root, long long lo, long long hi){
        if(!root) return true;
        if(lo >= root -> val || hi <= root -> val) return false;
        return f(f,root->left,lo, root -> val) && f(f, root->right, root->val, hi);
    };
    return f(f, root, -inf, inf);
}

Recover BST from pre-order

note that it’ll be unique if the elements are unique

pre-order traversal is usual dfs like where you print on entry

Start with an inf right bound and keep on adding to left if we are withing bound, else returning to parent.

TreeNode* bstFromPreorder(vector<int>& pre) {
    int idx = 0;
    // only -inf, hi) is in range
    auto f = [&](auto&& f, int hi) -> TreeNode* {
        if(idx == (int)pre.size() || pre[idx] >= hi) return nullptr;
        TreeNode* root = new TreeNode(pre[idx++]);
        root -> left = f(f, root -> val);
        root -> right = f(f, hi);
        return root;
    };
    return f(f, (int)1e9);
}