Inorder invariant

Inorder traversal ( left → root → right ) is strictly increasing, that much is obvious. But, a tree is a BST iff inorder traversal is strictly increasing.

Why? [left subtree] < x < [right subtree] If the invariant holds recursively, you can say all nodes in left subtree < x < all nodes in right subtree

Is Valid BST ( another solution )

bool isValidBST(TreeNode* root) {
    long long prev = LLONG_MIN;
 
    auto f = [&](auto&& f, TreeNode* root) -> bool {
        if (!root) return true;
        if (!f(f, root->left)) return false;
        if (prev >= root->val) return false;
        prev = root->val;
        return f(f, root->right);
    };
 
    return f(f, root);
}

Kth smalles value in BST

Notice the early termination and the compact style

int kthSmallest(TreeNode* root, int k) {
    int ans;
 
    auto f = [&](auto&& f, TreeNode* root) -> bool {
        if (!root) return false;
        if (f(f, root->left)) return true;
        if (--k == 0) return ans = root->val, true;
        return f(f, root->right);
    };
 
    f(f, root);
    return ans;
}

Recover BST

The trick part is handling both two and one inversion case cleanly.

2 inversion case
valid:   1 2 3 4 5 6
swapped: 1 5 3 4 2 6
           ↑     ↑

inversion 1
5 > 3
inversion 2
4 > 2

what got swapped? if cur is the RHS val
prev of cur ( inv1 ) and cur ( inv2 )

1 inversion case
valid:   1 2 3
swapped: 1 3 2

inversion
3 > 2
prev of cur AND the cur

so you can only set the first one on the first inv and keep on
updating the second one

void recoverTree(TreeNode* root) {
    // inversions in inorder traversal
 
    // note: you cannot do TreeNode* prev, first, second
    // * associates with the var not type
    TreeNode *prev, *first, *second;
    prev = first = second = nullptr;
    auto f = [&](auto&& f, TreeNode* root) {
        if(!root) return;
        f(f,root->left);
        if(prev && prev -> val > root->val){
            if(!first) first = prev;
            second = root;
        }
        prev = root;
        f(f,root->right);
    };
    f(f,root);
    swap(first -> val, second -> val);
}