## 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;
}
};
```

The post Validate Binary Search Tree appeared first on Coder's Cat.

## Discussion (0)