75. Check if a tree is a BST or not

Given the root node of a binary tree. Return true if the given binary tree is a binary search tree(BST) else false.

A valid BST is defined as follows:

  • The left subtree of a node contains only nodes with key strictly less than the node's key.
  • The right subtree of a node contains only nodes with key strictly greater than the node's key.
  • Both the left and right subtrees must also be binary search trees.

Example 1:

Input : root = [5, 3, 6, 2, 4, null, 7]

Output : true

Explanation :

Below is image of the given tree.

Example 2:

Input : root = [5, 3, 6, 4, 2, null, 7]

Output : false

Explanation :

Below is image of the given tree.

The node 4 and node 2 violates the BST rule of smaller to left and larger to right.

Now Your Turn!

Pick the correct output for the given input

Input : root = [2, 1, 3]

Still unsure what the problem is asking ?

Let’s go through a few more examples, step by step, to make it clearer.

Constraints:

  • 1 <= Number of Nodes <= 104
  • -231 <= Node.val <= 231 - 1

Hints

Frequently Occurring Doubts

Interview Follow-up Questions

Fun Facts

0
/**
* Definition for a binary tree node.
* struct TreeNode {
* int data;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int val) : data(val) , left(nullptr) , right(nullptr) {}
* };
**/
 
class Solution{
public:
bool isBST(TreeNode* root){
//your code goes here
}
};
Test Case

Input:

Root
to save your code