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;
}
Are there any code examples left?
New code examples in category C++
-
C++ 2023-04-28 17:44:25
-
C++ 2022-03-27 19:20:39 lists occurrences of characters in the string c++
-
C++ 2022-03-27 18:00:14 variabili in c++
-
C++ 2022-03-27 17:10:08 repeat character n times c++
-
C++ 2022-03-27 15:50:07 delete an array c++
-
C++ 2022-03-27 15:40:12 C++ pointer to base class
-
C++ 2022-03-27 12:15:21 find the graph is minimal spanig tree or not
-
C++ 2022-03-27 11:30:15 multi variable assignment cpp
-
C++ 2022-03-27 11:05:17 c++ pi float
-
C++ 2022-03-27 10:20:12 why exceptions can lead to memory leaks