Check if a binary tree is BST or not

Delete a node in binary search tree

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.

New Comment







© 2021, kalkicode.com, All rights reserved