Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key. Both the left and right subtrees must also be binary search trees.

Example 1:
    2
   / \
  1   3
Binary tree [2,1,3], return true.

Example 2:
    1
   / \
  2   3
Binary tree [1,2,3], return false.

Solution: Using Recursion

A binary search tree has the following properties:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.
• Each node (item in the tree) has a distinct key.

For each node we need to know its range (min, max).

bool isValidBSTUtil(TreeNode *root, TreeNode *min, TreeNode *max) {
    if (!root) return true;

    if (min && root->val <= min->val) return false;
    if (max && root->val >= max->val) return false;
    return isValidBSTUtil(root->left, min, root) && isValidBSTUtil(root->right, root, max);
}

bool isValidBST(TreeNode* root) {
    return isValidBSTUtil(root, NULL, NULL);
}

Solution: Using inorder ascending property of BST

We can store the address of the previous node

    bool isValidBSTUtil(TreeNode *root, TreeNode **prev) {
        if (!root) return true;

        if (!isValidBSTUtil(root->left, prev)) return false;

        if (*prev && root->val <= (*prev)->val) return false;

        *prev = root;
        return isValidBSTUtil(root->right, prev);
    }

    bool isValidBST(TreeNode* root) {
        TreeNode *prev = NULL;
        return isValidBSTUtil(root, &prev);
    }