# Check if a binary tree is BST or not

Here given code implementation process.

``````/*
C Program
+ Check if a binary tree is BST or not
*/
#include <stdio.h>
#include <stdlib.h>
//structure of Binary Tree node
struct Node
{
int data;
struct Node*left,*right;
};
//Create a binary tree nodes
struct Node* insert(int data)
{
//create dynamic memory to new binary tree node
struct Node*new_node=(struct Node*)malloc(sizeof(struct Node));
if(new_node!=NULL)
{
//set data and pointer values
new_node->data=data;
//Initially node left-pointer is NULL
new_node->left=NULL;
//Initially node right-pointer is NULL
new_node->right=NULL;
}else
{
printf("Memory Overflow\n");
exit(0); //Terminate program execution
}
//return reference
return new_node;

}
//Display tree element inorder form
void inorder(struct Node*node)

{

if(node)
{

inorder(node->left);
//Print node value
printf("  %d",node->data);
inorder(node->right);
}

}
int is_bst(struct Node*root,struct Node*left_p,struct Node*right_p)
{
if(root!=NULL)
{

if( left_p != NULL && left_p->data > root->data ||
right_p != NULL && right_p->data < root->data)
{

return 0;
}

return (is_bst(root->left,left_p,root) &&
is_bst(root->right,root,right_p)
);
}
return 1;
}
int main()
{

struct Node*root=NULL;
/*  Make A Binary Tree
-----------------------
15
/  \
10   24
/    /  \
9   16    30
*/
//Insertion of binary tree nodes
root               = insert(15);
root->left         = insert(10);
root->right        = insert(24);
root->right->right = insert(30);
root->right->left  = insert(16);
root->left->left   = insert(9);

//Display Tree elements
inorder(root);

if(is_bst(root,NULL,NULL))
{
printf("\n  Yes \n" );
}
else
{
printf("\n  No \n" );
}
/*  Add new node 25 in binary tree
-----------------------
15
/  \
10   24
/    /  \
9   16    30
\
25
*/

root->right->left->right  = insert(25);

//Display Tree elements
inorder(root);
if(is_bst(root,NULL,NULL))
{
printf("\n  Yes \n" );
}
else
{
printf("\n  No \n" );
}

return 0;
}
``````

#### Output

``````  9  10  15  16  24  30
Yes
9  10  15  16  25  24  30
No
``````
``````/*
C++ Program
+ Check if a binary tree is BST or not
*/
#include <iostream>
using namespace std;

//Structure of Binary Tree node
class Node
{
public:
int data;
Node*left,*right;
//make a tree node
Node(int data)
{
//assign field values
this->data=data;
left=right=NULL;
}
};

class BinaryTree
{
public:
Node*root;
BinaryTree();
void inorder(Node*);
int is_bst( Node*, Node*, Node*);
};

//set initial tree root to NULL
BinaryTree:: BinaryTree()
{
root=NULL;
}

//Display tree element inorder form
void BinaryTree::inorder(Node*node)
{

if(node)
{

inorder(node->left);
//Print node value
cout<<"  "<<node->data;
inorder(node->right);
}
}

int BinaryTree:: is_bst( Node*root, Node*left_p, Node*right_p)
{
if(root!=NULL)
{
if( left_p != NULL && left_p->data > root->data ||
right_p != NULL && right_p->data < root->data)
{
return 0;
}
return (is_bst(root->left,left_p,root) &&
is_bst(root->right,root,right_p)
);
}
return 1;
}
int main(){

BinaryTree obj;

/*  Make A Binary Tree
-----------------------
15
/  \
10  24
/  /  \
9  16  30
*/
//insert of binary tree nodes
obj.root  = new Node(15);
obj.root->left  =new Node(10);
obj.root->right  =new Node(24);
obj.root->right->right =new Node(30);
obj.root->right->left  =new Node(16);
obj.root->left->left  = new Node(9);
//Display Tree elements
obj.inorder(obj.root);
if(obj.is_bst(obj.root,NULL,NULL))
{
cout<<("\n  Yes \n" );
}
else
{
cout<<("\n  No \n" );
}
/*  Add new node 25 in binary tree
-----------------------
15
/  \
10   24
/   /   \
9   16   30
\
25
*/
obj.root->right->left->right  = new Node(25);
//Display Tree elements
obj.inorder(obj.root);
if(obj.is_bst(obj.root,NULL,NULL))
{
cout<<("\n  Yes \n" );
}
else
{
cout<<("\n  No \n" );
}

return 0;
}``````

#### Output

``````  9  10  15  16  24  30
Yes
9  10  15  16  25  24  30
No``````
``````/*
Java Program
Check if a binary tree is BST or not
*/

//Structure of Binary Tree node
class Node
{

int data;
Node left, right;
//make a tree node
public Node(int data)
{
//assign field values
this.data=data;
left=right=null;
}
}

public class BinaryTree
{

public Node root;

public BinaryTree()
{
//set initial tree root to null
root=null;
}
//Display tree element inorder form
public void inorder(Node node)
{

if(node!=null)
{
inorder(node.left);
//Print node value
System.out.print("  "+node.data);
inorder(node.right);
}

}

public boolean  is_bst( Node root, Node left_p, Node right_p)
{
if(root!=null)
{
if( left_p != null && left_p.data > root.data ||
right_p != null && right_p.data < root.data)
{
return false;
}
return (is_bst(root.left,left_p,root) &&
is_bst(root.right,root,right_p)
);
}
return true;
}
public static void main(String[] args)
{
//Make object of Binary Tree
BinaryTree obj=new BinaryTree();

/*   Make A Binary Tree
-----------------------
15
/  \
10  24
/  /  \
9  16  30
*/
//insert of binary tree nodes
obj.root  = new Node(15);
obj.root.left  =new Node(10);
obj.root.right  =new Node(24);
obj.root.right.right =new Node(30);
obj.root.right.left  =new Node(16);
obj.root.left.left  = new Node(9);
//Display Tree elements
obj.inorder(obj.root);
if(obj.is_bst(obj.root,null,null))
{
System.out.println("\n  Yes " );
}
else
{
System.out.println("\n  No " );
}
/*  Add new node 25 in binary tree
-----------------------
15
/  \
10   24
/   /   \
9   16   30
\
25
*/
obj.root.right.left.right  = new Node(25);
//Display Tree elements
obj.inorder(obj.root);
if(obj.is_bst(obj.root,null,null))
{
System.out.println("\n  Yes " );
}
else
{
System.out.println("\n  No " );
}

}
}``````

#### Output

``````  9  10  15  16  24  30
Yes
9  10  15  16  25  24  30
No
``````
``````#Python Program
#Check if a binary tree is BST or not

class Node :
def __init__(self,data):
#Assign node value
self.data=data
self.left=None
self.right=None

class BinaryTree :

def __init__(self):
#set initial tree root to null
self.root=None

#Display tree element inorder form
def inorder(self,node) :
if(node!=None) :
self.inorder(node.left)
#Print node value
print(node.data,end="  ")
self.inorder(node.right)

def is_bst(self, root, left_p, right_p) :

if(root!=None) :

if( left_p != None  and  left_p.data > root.data or
right_p!= None  and  right_p.data < root.data) :

return False

return ( self.is_bst( root.left,left_p,root)  and
self.is_bst(root.right,root,right_p))

return True

def main():
#Make object of Binary Tree
obj=BinaryTree()

# Make A Binary Tree
#
#      15
#     /  \
#    10  24
#   /   /   \
#  9   16   30
#
#insert of binary tree nodes
obj.root  =  Node(15)
obj.root.left  = Node(10)
obj.root.right  = Node(24)
obj.root.right.right = Node(30)
obj.root.right.left  = Node(16)
obj.root.left.left  =  Node(9)
#Display Tree elements
obj.inorder(obj.root)
if(obj.is_bst(obj.root,None,None)==True) :

print ("\nYes " )
else :
print("\nNo " )
# Add  node 25 in binary tree
#
#      15
#     /  \
#    10   24
#   /   /   \
#  9   16   30
#        \
#        25
#
obj.root.right.left.right  =  Node(25)
#Display Tree elements
obj.inorder(obj.root)
if(obj.is_bst(obj.root,None,None)==True) :

print("\nYes " )
else :

print("\nNo " )
if __name__=="__main__":
main()``````

#### Output

``````9  10  15  16  24  30
Yes
9  10  15  16  25  24  30
No
``````
``````/*
C# Program
Check if a binary tree is BST or not
*/

using System;
// Binary Tree node
public class Node
{

public int data;
public Node left, right;
//make a tree node
public Node(int data)
{
//assign field values
this.data=data;
left=right=null;
}
}

public class BinaryTree
{

public Node root;

public BinaryTree()
{
//set initial tree root to null
root=null;
}
//Display tree element inorder form
public void inorder(Node node)
{

if(node!=null)
{
inorder(node.left);
//Print node value
Console.Write("  "+node.data);
inorder(node.right);
}

}

public Boolean  is_bst( Node root, Node left_p, Node right_p)
{
if(root!=null)
{
if( left_p != null && left_p.data > root.data ||
right_p != null && right_p.data < root.data)
{
return false;
}
return (is_bst(root.left,left_p,root) &&
is_bst(root.right,root,right_p)
);
}
return true;
}
public static void Main(String[] args)
{
//Make object of Binary Tree
BinaryTree obj=new BinaryTree();

/*   Make A Binary Tree
-----------------------
15
/  \
10  24
/  /  \
9  16  30
*/
//insert of binary tree nodes
obj.root  = new Node(15);
obj.root.left  =new Node(10);
obj.root.right  =new Node(24);
obj.root.right.right =new Node(30);
obj.root.right.left  =new Node(16);
obj.root.left.left  = new Node(9);
//Display Tree elements
obj.inorder(obj.root);
if(obj.is_bst(obj.root,null,null))
{
Console.WriteLine("\n  Yes " );
}
else
{
Console.WriteLine("\n  No " );
}
/*  Add new node 25 in binary tree
-----------------------
15
/  \
10   24
/   /   \
9   16   30
\
25
*/
obj.root.right.left.right  = new Node(25);
//Display Tree elements
obj.inorder(obj.root);
if(obj.is_bst(obj.root,null,null))
{
Console.WriteLine("\n  Yes " );
}
else
{
Console.WriteLine("\n  No " );
}

}
}
``````

#### Output

``````  9  10  15  16  24  30
Yes
9  10  15  16  25  24  30
No ``````
``````<?php
//Php program
//Inorder Tree Traversal of a Binary Tree
//using recursion
class Node
{
public \$data;
public \$left;
public \$right;
function __construct(\$data)
{
\$this->data = \$data;
\$this->left = NULL;
\$this->right = NULL;
}
}
class BinaryTree
{

public \$root;
function __construct()
{
//set initial tree root to null
\$root=NULL;
}

//Display all inserted node in linked list
public function inorder(\$node)
{
if(\$node!=NULL)
{
\$this->inorder(\$node->left);
//Print node value
echo "  ".\$node->data;
\$this->inorder(\$node->right);
}
}
public function is_bst( \$root, \$left_p, \$right_p)
{
if(\$root!=NULL)
{
if( \$left_p != NULL && \$left_p->data > \$root->data||
\$right_p!= NULL && \$right_p->data < \$root->data)
{
return true;
}
return ( \$this->is_bst( \$root->left,\$left_p,\$root) &&
\$this->is_bst(\$root->right,\$root,\$right_p)
);
}
return false;
}
}
function main()
{

\$obj= new BinaryTree();

# Make A Binary Tree
# -----------------------
#      15
#     /  \
#    10  24
#   /   /   \
#  9   16   30
#
//insert of binary tree nodes
\$obj->root  = new Node(15);
\$obj->root->left  =new Node(10);
\$obj->root->right  =new Node(24);
\$obj->root->right->right =new Node(30);
\$obj->root->right->left  =new Node(16);
\$obj->root->left->left  = new Node(9);
//Display Tree elements
\$obj->inorder(\$obj->root);
if(\$obj->is_bst(\$obj->root,NULL,NULL))
{
echo ("\n  Yes \n" );
}
else
{
echo("\n  No \n" );
}

# Add new node 25 in binary tree
# -----------------------
#      15
#     /  \
#    10   24
#   /   /   \
#  9   16   30
#        \
#        25
#

\$obj->root->right->left->right  = new Node(25);
//Display Tree elements
\$obj->inorder(\$obj->root);
if(\$obj->is_bst(\$obj->root,NULL,NULL))
{
echo("\n  Yes \n" );
}
else
{
echo("\n  No \n" );
}
}
main();
?>``````

#### Output

``````  9  10  15  16  24  30
No
9  10  15  16  25  24  30
No
``````

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.