Binary Serach tree is binary tree. code example

Example 1: 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; 
}

Example 2: binary tree search

/* This is just the seaching function you need to write the required code.
	Thank you. */

void searchNode(Node *root, int data)
{
    if(root == NULL)
    {
        cout << "Tree is empty\n";
        return;
    }

    queue<Node*> q;
    q.push(root);

    while(!q.empty())
    {
        Node *temp = q.front();
        q.pop();

        if(temp->data == data)
        {
            cout << "Node found\n";
            return;
        }

        if(temp->left != NULL)
            q.push(temp->left);
        if(temp->right != NULL)
            q.push(temp->right);
    }

    cout << "Node not found\n";
}