# Validate Binary Search Tree

Oct 23, 2017

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.

 long long vmax = LLONG_MIN;
bool isValidBST1(TreeNode* root) {
if (root == NULL) return true;
if ( !isValidBST(root->left) ) return false;
if (root->val <= vmax) return false;
vmax = root->val;
return isValidBST(root->right);
}


long long vmax = LLONG_MIN;
bool isValidBST(TreeNode* root) {
stack<TreeNode *> st;
while(true) {
while(root){
st.push(root);
root = root->left;
}

if (st.empty()) break;
root = st.top();
st.pop();

if (vmax >= root->val) return false;
vmax = root->val;

root = root->right;
}
return true;
}


bool isValidBST(TreeNode* root) {
TreeNode* prev = NULL;
return validate(root, prev);
}
bool validate(TreeNode* node, TreeNode* &prev) {
if (node == NULL) return true;
if (!validate(node->left, prev)) return false;
if (prev != NULL && prev->val >= node->val) return false;
prev = node;
return validate(node->right, prev);
}

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

bool isValidBST(TreeNode* root, TreeNode* minNode, TreeNode* maxNode) {
if(!root) return true;
if(minNode && root->val <= minNode->val || maxNode && root->val >= maxNode->val)
return false;
return isValidBST(root->left, minNode, root) && isValidBST(root->right, root, maxNode);
}

LeetCodeLeetCode

Binary Tree Level Order Traversal

Unique Binary Search Tree