# Validate Binary Search Tree

## Challenge Description

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.

## Recursive Algorithm

For checking the property of every node in search tree, we recursive traverse all the nodes.

We use a rec helper function with two more extra parameters as the left bounder and right bounder node.

class Solution {
public:

bool rec(TreeNode* root, TreeNode* min, TreeNode* max) {
if(root == NULL)
return true;

if ((min != NULL && root->val <= min->val) ||
(max != NULL && root->val >= max->val))
return false;

return rec(root->left, min, root) && rec(root->right, root, max) ;
}

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

## Traverse binary tree with inorder

For the property of BST, if we traverse the tree in the inorder, it will be a increasing sequence. Add a varaible name of pre to store the previous tree node.

If it is not a valid binary search tree, this property will not hold.

class Solution {
public:
TreeNode* pre;

bool in_order(TreeNode* cur) {
if(cur == NULL) return true;
if(cur->left && !in_order(cur->left))
return false;
if(pre != NULL && pre->val >= cur->val)
return false;
pre = cur;
if(cur->right && !in_order(cur->right))
return false;
return true;
}

bool isValidBST(TreeNode* root) {
pre = NULL;
return in_order(root);
}
};

We can also use a stack to implement a iteractive algorithm:

class Solution {
public:
bool isValidBST(TreeNode* root) {
TreeNode* pre = NULL;
stack<TreeNode*> stack;
TreeNode* cur = root;
while(!stack.empty() || cur != NULL) {
if(cur != NULL) {
stack.push(cur);
cur = cur->left;
} else {
cur = stack.top();
if(pre != NULL && pre->val >= cur->val)
return false;
pre = cur;
stack.pop();
cur = cur->right;
}
}
return true;
}
};
Last Updated on