How To Check If A Tree Is Bst Code Example

Example 1: check if binary search tree is valid

class BTNode {   constructor(value) {     this.value = value;     this.left = null;     this.right = null;   } }  /**  *  * @param {BTNode} tree  * @returns {Boolean}  */ const isBinarySearchTree = (tree) => {   if (tree) {     if (       tree.left &&       (tree.left.value > tree.value || !isBinarySearchTree(tree.left))     ) {       return false;     }     if (       tree.right &&       (tree.right.value <= tree.value || !isBinarySearchTree(tree.right))     ) {       return false;     }   }   return true; };

Example 2: check for bst

// C++ program to check if a given tree is BST.  #include <bits/stdc++.h>  using namespace std;   /* A binary tree node has data, pointer to  left child and a pointer to right child */ struct Node  {  	int data;  	struct Node* left, *right;  };   // Returns true if given tree is BST.  bool isBST(Node* root, Node* l=NULL, Node* r=NULL)  {  	// Base condition  	if (root == NULL)  		return true;   	// if left node exist then check it has  	// correct data or not i.e. left node's data  	// should be less than root's data  	if (l != NULL and root->data <= l->data)  		return false;   	// if right node exist then check it has  	// correct data or not i.e. right node's data  	// should be greater than root's data  	if (r != NULL and root->data >= r->data)  		return false;   	// check recursively for every node.  	return isBST(root->left, l, root) and  		isBST(root->right, root, r);  }   /* Helper function that allocates a new node with the  given data and NULL left and right pointers. */ struct Node* newNode(int data)  {  	struct Node* node = new Node;  	node->data = data;  	node->left = node->right = NULL;  	return (node);  }   /* Driver program to test above functions*/ int main()  {  	struct Node *root = newNode(3);  	root->left	 = newNode(2);  	root->right	 = newNode(5);  	root->left->left = newNode(1);  	root->left->right = newNode(4);   	if (isBST(root,NULL,NULL))  		cout << "Is BST";  	else 		cout << "Not a BST";   	return 0;  }