Validate Binary Search Tree

Q:

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.

T:

We can do in-order traverse of the tree. All we need is to add an additional checking to see that whether the currently visited node is greater than its previously visited node. We can use a global variable to store previously visited node.

A:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode * prev = NULL;
    bool isValidBST(TreeNode *root) {
        if(root == NULL) {
            return true;
        }
        if(!isValidBST(root->left)) {
            return false;
        }
        if(prev != NULL && prev->val >= root->val) {
            return false;
        }
        prev = root;
        return isValidBST(root->right);
    }
};