# Validate Binary Search Tree – Leetcode Solution

In this post, we are going to solve the 98. Validate Binary Search Tree problem of Leetcode. This problem 98. Validate Binary Search Tree is a Leetcode medium level problem. Let’s see the code, 98. Validate Binary Search Tree – Leetcode Solution.

Contents

## Problem

Given the `root` of a binary tree, determine if it is a valid binary search tree (BST).

A valid 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: root = [2,1,3]
Output: true``````

### Example 2 :

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

### Constraints

• The number of nodes in the tree is in the range `[1, 104]`.
• `-231 <= Node.val <= 231 - 1`

Now, let’s see the code of 98. Validate Binary Search Tree – Leetcode Solution.

# Validate Binary Search Tree– Leetcode Solution

### 98. Validate Binary Search Tree – Solution in Java

```/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root) {
if(root == null) return true;

TreeNode curr = root;
TreeNode prev = null;
Stack<TreeNode> stack = new Stack<>();

while(curr != null || !stack.isEmpty()){
while(curr != null){
stack.push(curr);
curr = curr.left;
}

curr = stack.pop();
if(prev != null && curr.val <= prev.val) return false;

prev = curr;
curr = curr.right;
}
return true;
}
}```

### 98. Validate Binary Search Tree – Solution in C++

```/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isValidBST(TreeNode* root) {
long pre = LONG_MIN;
stack<TreeNode*> todo;
while (root || !todo.empty()) {
while (root) {
todo.push(root);
root = root -> left;
}
root = todo.top();
todo.pop();
if (root -> val <= pre) {
return false;
}
pre = root -> val;
root = root -> right;
}
return true;
}
};```

### 98. Validate Binary Search Tree– Solution in Python

```# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
def isValidBST(self, root):
pre, stack = None, []
while True:
while root:
stack.append(root)
root = root.left
if not stack:
return True
node = stack.pop()
if pre and pre.val >= node.val:
return False
pre = node
root = node.right
```

Note: This problem 98. Validate Binary Search Tree is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.