**Problem Statement:** You are given the root of a binary tree. The task is to determine if the given binary tree qualifies as a binary search tree.

Conditions for a Binary Tree to qualify as Binary Search Tree (BST):

- The left child’s key is
**less**than the key of its parent. - The right child’s key is
**more**than the key of its parent. - The left and right subtrees also count as BST individually.

**Example 1:**

**Input**: Address of root node given

**Output:** True

**Explanation**: Since the above Binary tree obeys all the conditions of BST return true.

**Example 2:**

**Input:** Address of root node given.

**Output:** False

**Explanation**: The root contains key 7, hence its left subtree should have nodes containing a key less than 7 but there is a node having its key as 9. This violates the principle of BST.

**Solution**

** Disclaimer**:

*Don’t jump directly to the solution, try it out yourself first.*

** Pre-requisites**: Recursion,

*Tree traversal techniques*

**Solution 1: **

**Initial thoughts**: Let us assume we have a node X. To check for BST, X’s key should not only be compared with its immediate left and right children but also its entire left and right subtree. So checking the entire left and right subtree for every node in a tree will be very inefficient.

**Approach: **The efficient method to solve this problem in a single traversal is discussed below:-

- Before visiting every node, a range is assigned to it. The lower bound and upper bound of the range is passed as parameters to the function.
- While visiting the node observe if the node’s key lies between the upper and lower bound.
- If not, return a false without any further traversal.
- If yes, make recursion calls once for the left subtree and right subtree of the node.

- Once we reach null, return true.

**NOTE**: The lower bound of the starting range is a minimum integer, say INT_MIN, and the upper bound is a maximum integer, say INT_MAX because the root’s key can have any value.

Have a look at the dry run for a better understanding.

- Start with root(key = 7) and the said initial range. INT_MIN < 7 < INT_MAX. Continue traversal.
- Arrive at
**node with key 5**with [INT_MIN,7] as range.INT_MIN < 5 < 7.Continue traversal. - Arrive at
**a node with key 3**with [INT_MIN, 5] as a range. INT_MIN < 3 < 5. Continue traversal. - Reaches NULL. Return true.
- Arrive at the
**node with key 6**with [5, 7] as a range. 5 < 6 < 7. Continue traversal. - Reaches NULL. Return true.
- Arrive at a
**node with key 10**with [7, INT_MAX] as the range. 7 < 10 < INT_MAX. Continue traversal. - Arrive at a
**node with key 4**with [7, 10] as the range. 4**does not**lie in the range. Do not continue traversal, return false.

**Code:**

## C++ Code

```
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node * left, * right;
Node(int val) {
data = val;
left = NULL;
right = NULL;
}
};
class Solution {
public:
bool isValidBST(Node * root) {
return solve(root, INT_MIN, INT_MAX);
}
bool solve(Node * root, int minVal, int maxVal) {
if (root == NULL) return true;
if (root -> data >= maxVal || root -> data <= minVal) return false;
return solve(root -> left, minVal, root -> data) && solve(root -> right,
root -> data, maxVal);
}
};
int main() {
Node * root = new Node(7);
root -> left = new Node(5);
root -> left -> left = new Node(3);
root -> left -> right = new Node(6);
root -> right = new Node(10);
root -> right -> left = new Node(4);
root -> right -> right = new Node(15);
Solution ob;
bool ans = ob.isValidBST(root);
if (ans == true) {
cout << "Valid BST";
} else {
cout << "Invalid BST";
}
return 0;
}
```

**Output:** Invalid BST

**Time Complexity: O(N) **for traversing N nodes.

**Space Complexity: O(1) **if** **we ignore the auxiliary stack space**.**

## Java Code

```
import java.util.*;
public class Main {
public static void main(String[] args) {
Node root = new Node(7);
root.left = new Node(5);
root.left.left = new Node(3);
root.left.right = new Node(6);
root.right = new Node(10);
root.right.left = new Node(9);
root.right.right = new Node(15);
Solution ob = new Solution();
boolean ans = ob.isValidBST(root);
if (ans == true) {
System.out.print("Valid BST");
} else {
System.out.print("Invalid BST");
}
}
}
class Node {
int data;
Node left, right;
Node(int data) {
this.data = data;
left = null;
right = null;
}
}
class Solution {
private boolean checkBST(Node node, long min, long max) {
if (node == null) return true;
if (node.data <= min || node.data >= max) return false;
if (checkBST(node.left, min, node.data) && checkBST(node.right, node.data,
max))
{
return true;
}
return false;
}
public boolean isValidBST(Node root) {
return checkBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
}
```

**Output:** Valid BST

**Time Complexity: O(N) **for traversing N nodes.

**Space Complexity: O(1) **if** **we ignore the auxiliary stack space**.**

Special thanks toplease check out this articlefor contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam,Somparna Chakrabarti