# 98. 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.

Example 1:

``````Input:

2
/ \
1   3

Output:
true
``````

Example 2:

``````    5
/ \
1   4
/ \
3   6

Output:
false

Explanation:
The input is: [5,1,4,null,null,3,6]. The root node's value
is 5 but its right child's value is 4.
``````

Thoughts:

1. Inorder traversal + checking ascending property in serialized array
2. Improving 1 by only recording the prev node
3. Iteratively defining the left and right bound of the node
4. Iterative Traversal (Generic to solve other problems such as Binary Tree Inorder Traversal, Kth Smallest in BST and Validate BST

Code 2:

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isValidBST(TreeNode* root) {
TreeNode * prev = NULL;
return isValidBST(root, prev);
}
private:
bool isValidBST(TreeNode * root, TreeNode* & prev){ // !!important to add "&" since the prev will be changed
// as traversing down the BST
if(root == NULL) return true;
if(!isValidBST(root->left, prev)) return false;
if(prev != NULL && prev ->val >= root-> val) return false;
prev = root;
return isValidBST(root->right, prev);
}
};
``````

Code 3:

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root) {
return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

public boolean isValidBST(TreeNode root, long min, long max){
if(root == null) return true;
if(root.val >= max || root.val <= min) return false;
return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);
}
}
``````

Code 4:

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root) {
if(root == null) return true;
Stack<TreeNode> stack = new Stack<>();
TreeNode pre = null;
while (root != null || !stack.isEmpty()){
// left
while(root != null){
stack.push(root);
root = root.left;
}
root = stack.pop();
// do
if (pre!= null && pre.val >= root.val) return false;
// record predecessor
pre = root;
// right
root = root.right;
}

return true;
}
}
``````

Kth Smallest Element in a BST

`````` public int kthSmallest(TreeNode root, int k) {
Stack<TreeNode> stack = new Stack<>();
while(root != null || !stack.isEmpty()) {
while(root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if(--k == 0) break;
root = root.right;
}
return root.val;
}
``````

Binary Tree Inorder Traversal

``````public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null) return list;
Stack<TreeNode> stack = new Stack<>();
while(root != null || !stack.empty()){
while(root != null){
stack.push(root);
root = root.left;
}
root = stack.pop();