[LeetCode] Validate Binary Search Tree

Link : 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.

Analysis:
The first thing to make clear is whether there is duplicate element in the tree. If there, is it correct to put it in the left subtree, or in the right subtree.

1). A quick solution would be use range comparison, from top to bottom, and return validity from bottom to top. Code
2). A second option would be in-order DFS. Code


Using range comparison

 class Solution {
    public:
    bool isValidBST(TreeNode *root) {
        if(root==NULL)
        return true;
        return helper(root, INT_MIN, INT_MAX);
    }
    
    bool helper(TreeNode* root, int low, int high)
    {
        if(root==NULL)
        return true;
        if( low>high || root->val < low || root->val > high)
        return false;
        return helper(root->left, low, root->val-1) && helper(root->right, root->val+1, high);
    }
};

Using inorder DFS

class Solution {
    public:
    bool isValidBST(TreeNode *root) {
        if(root==NULL)
        return true;
        pre==NULL;
        valid=true;
        check(root);
        return valid;
    }
    
    void check(TreeNode* root)
    {
        if(root==NULL||valid==false)
        return;
        check(root->left);
        if(valid==false) return; // to skip following if BST is invalid
        if(pre!=NULL) // if there is a previous node
        valid &= (pre->val<root->val);
        pre = root; // record this node as pre for next comparison
        check(root->right);
    }
    
    private:
    TreeNode* pre;
    bool valid;
};