Check if array is inorder of BST

Check if array is inorder of BST

Here given code implementation process.

//C Program 
//Check if array is inorder of bst
#include <stdio.h>
#include <stdlib.h>
//structure of Binary Search Tree node
struct Node
{
  int data;
  struct Node *left,*right; 
};

//Adding a new node in binary search tree
void add( struct Node **root, int data)
{
  //Create a dynamic node of binary search tree 
  struct Node *new_node = (struct Node *)malloc(sizeof(struct Node ));

  if(new_node!=NULL)
  {
    //Set data and pointer values
    new_node->data = data;
    new_node->left = NULL; //Initially node left-pointer is NULL
    new_node->right = NULL;//Initially node right-pointer is NULL

    if(*root == NULL)
    {
      //When adds a first node in binary tree
      *root = new_node;
    }
    else
    {
      struct Node *find = *root;
      //iterate binary tree and add new node to proper position
      while(find != NULL)
      {
        if(find -> data > data)
        { 
          if(find->left==NULL)
          {
            find->left = new_node;
            break;
          }
          else
          { //visit left sub-tree
            find = find->left;
          }
        }
        else
        {
          if(find->right == NULL)
          {
            find->right = new_node;
            break;
          }
          else
          {
            //visit right sub-tree
            find = find->right;
          }
        }
      }
    }
  }else
  {
    printf("Memory Overflow\n");
    exit(0); //Terminate program execution
  }

}


int is_bst_inorder(struct Node*root,int sequence[],int *counter,int size)
{
  if(root != NULL)
  {
    
    int a = is_bst_inorder(root->left,sequence,counter,size);

    if(*counter < size && sequence[*counter] != root->data) 
    {
      return 0;
    }
    (*counter)++;
    int b = is_bst_inorder(root->right,sequence,counter,size);
    if (a==0 || b==0)
    {
      return 0;
    }

  }
  return 1;
}
void bst_inorder(struct Node*root,int sequence[],int size)
{
  if(size<0) return;

  if(root!=NULL)
  {
    
    int counter=0;
    printf("\n Sequence : ");
    for (int i = 0; i < size; ++i)
    {
      printf("%d  ",sequence[i] );
    }
    if(is_bst_inorder(root,sequence,&counter,size))
    {
      if(counter!=size)
      {
        printf("Is Not inorder\n");
      }
      else
      {
        printf("Is inorder\n");
      }
    }
    else
    {
      printf("Is Not inorder\n");
    }
   
  }
  else
  {
    printf("Empty BST\n");
  }
}
void inorder(struct Node*root)
{
  if(root!=NULL)
  {
    inorder(root->left);
    printf("%d  ",root->data );
    inorder(root->right);
   
  }
}
int main(){
    
  struct Node*root = NULL;

  //Add nodes in binary search tree
  /*
             5
           /   \
          3     9
         / \   / \
        2   4 8   11
                 /
                10   

  */                

  add(&root,5); 
  add(&root,3); 
  add(&root,9); 
  add(&root,2); 
  add(&root,4); 
  add(&root,8); 
  add(&root,11); 
  add(&root,10); 
  
  printf(" Inorder : ");
  inorder(root);
  printf("\n");
  int sequence1[]={ 2,  3,  4,  5,  8, 9, 10};

  int size = sizeof(sequence1)/ sizeof(sequence1[0]);
  
  bst_inorder(root,sequence1,size);


  int sequence2[]={ 2,  3,  4,  5,   8, 9, 10,  11, 11 };

  size = sizeof(sequence2)/ sizeof(sequence2[0]);
  
  bst_inorder(root,sequence2,size);


  int sequence3[]={ 2,  3,  4,  5, 8, 9, 10,  11 };

  size = sizeof(sequence3)/ sizeof(sequence3[0]);
  
  bst_inorder(root,sequence3,size);



  return 0;
}

Output

 Inorder : 2  3  4  5  8  9  10  11  

 Sequence : 2  3  4  5  8  9  10  Is Not inorder

 Sequence : 2  3  4  5  8  9  10  11  11  Is Not inorder

 Sequence : 2  3  4  5  8  9  10  11  Is inorder
//C++ Program 
//Check if array is inorder of bst
#include <iostream>
using namespace std;
//structure of Binary Search Tree node
struct Node

{
  int data;
  struct Node *left,*right; 
};
class BST
{

public:
  Node*root;
  BST();
  //public methods
  void add(int);
  void inorder(Node*);
  int is_bst_inorder( Node*,int [],int *,int );
  void bst_inorder(int [],int );
  
};
BST::BST()
{
  root=NULL;
}
//Adding a new node in binary search tree
void BST :: add(int data)
{
  //Create a dynamic node of binary search tree 
   Node *new_node = new Node();

  if(new_node!=NULL)
  {
    //Set data and pointer values
    new_node->data = data;
    new_node->left = NULL; //Initially node left-pointer is NULL
    new_node->right = NULL;//Initially node right-pointer is NULL

    if(root == NULL)
    {
      //When adds a first node in binary tree
      root = new_node;
    }
    else
    {
       Node *find = root;

      //add new node to proper position
      while(find != NULL)
      {
        if(find -> data >= data)
        { 
          if(find->left==NULL)
          {
            find->left = new_node;
            break;
          }
          else
          { 
            //visit left sub-tree
            find = find->left;
          }
        }
        else
        {
          if(find->right == NULL)
          {
            find->right = new_node;
            break;
          }
          else
          {
            //visit right sub-tree
            find = find->right;
          }
        }
      }
    }
  }
  else
  {
    cout<<("Memory Overflow\n");
  }
}
void BST :: inorder(Node*root)
{
  if(root!=NULL)
  {
   
    inorder(root->left);
    inorder(root->right);
    cout<<"  "<< root->data;
  }
}
//Check if a given sequence is form of BST tree inorder
int BST :: is_bst_inorder( Node*root,int sequence[],int *counter,int size)
{
  if(root != NULL)
  {
    
    int a = is_bst_inorder(root->left,sequence,counter,size);

    if(*counter < size && sequence[*counter] != root->data) 
    {
      return 0;
    }
    (*counter)++;
    int b = is_bst_inorder(root->right,sequence,counter,size);
    if (a==0 || b==0)
    {
      return 0;
    }
  }
  return 1;
}
void BST :: bst_inorder(int sequence[],int size)
{
  if(size<0) return;

  if(root!=NULL)
  {
    
    int counter=0;
    cout<<("\n Sequence : ");
    for (int i = 0; i < size; ++i)
    {
      cout<<sequence[i]<< "  ";
    }
    if(is_bst_inorder(root,sequence,&counter,size))
    {
      if(counter!=size)
      {
        cout<<("is Not inorder\n");
      }
      else
      {
        cout<<("is inorder\n");
      }
    }
    else
    {
       cout<<("is Not inorder\n");
    }
   
  }
  else
  {
    cout<<("Empty BST\n");
  }
}
int main()
{

  BST obj;
  //Add nodes in binary search tree
  /*
             5
           /   \
          3     9
         / \   / \
        2   4 8   11
                 /
                10   
  */                
  obj.add(5); 
  obj.add(3); 
  obj.add(9); 
  obj.add(2); 
  obj.add(4); 
  obj.add(8); 
  obj.add(11); 
  obj.add(10); 
  cout<<"\n Inorder " ;
  obj.inorder(obj.root);
  cout<<("\n");

  //Test Case
  int sequence1[]={2,  3,  4,  5,  8, 9, 10};

  int size = sizeof(sequence1)/ sizeof(sequence1[0]);
  
  obj.bst_inorder(sequence1,size);


  int sequence2[]={2,  3,  4,  5,   8, 9, 10,  11, 11};

  size = sizeof(sequence2)/ sizeof(sequence2[0]);
  
  obj.bst_inorder(sequence2,size);


  int sequence3[]={2,  3,  4,  5, 8, 9, 10,  11};

  size = sizeof(sequence3)/ sizeof(sequence3[0]);
  
  obj.bst_inorder(sequence3,size);
  return 0;
}

Output

 Inorder   2  4  3  8  10  11  9  5

 Sequence : 2  3  4  5  8  9  10  is Not inorder

 Sequence : 2  3  4  5  8  9  10  11  11  is Not inorder

 Sequence : 2  3  4  5  8  9  10  11  is inorder
//Java program
//Check if array is inorder of bst
public class BST
{

  static class Node
  {
    int data;
    Node left,right;
  }
  public Node root;
  static int counter;

  //Class constructors
  BST()
  {
    root=null;
    counter=0;
  } 

  //insert  element
  public void add(int data)
  {
    //Create a dynamic node of binary search tree 
    Node new_node = new 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;

      if(root == null)
      {
        //When adds a first node in binary tree
        root = new_node;
      }
      else
      {
        Node find = root;

        //add new node to proper position
        while(find != null)
        {
          if(find.data >= data)
          { 
            if(find.left==null)
            {
              find.left = new_node;
              break;
            }
            else
            { 
              //visit left sub-tree
              find = find.left;
            }
          }
          else
          {
            if(find.right == null)
            {
              find.right = new_node;
              break;
            }
            else
            {
              //visit right sub-tree
              find = find.right;
            }
          }
        }
      }
    }
    else
    {
      System.out.println("Memory Overflow");
    }
  }

  //Check if a given sequence is form of BST tree inorder
  public boolean is_bst_inorder( Node root,int []sequence,int size)
  {
    if(root != null)
    {

      boolean a = is_bst_inorder(root.left,sequence,size);

      if( counter < size && sequence[ counter] != root.data) 
      {
        return false;
      }
      counter++;
      boolean b = is_bst_inorder(root.right,sequence,size);
      if (a==false || b==false)
      {
        return false;
      }
    }
    return true;
  }
  public void bst_inorder(int []sequence)
  {
    if(sequence.length<0)
    {
      return;
    }

    if(root!=null)
    {

      counter=0;
      int size = sequence.length;
      System.out.print("\n Sequence : ");
      for (int i = 0; i < size; ++i)
      {
        System.out.print(sequence[i]+ "  ");
      }
      if(is_bst_inorder(root,sequence,size))
      {
        if(counter!=size)
        {
          System.out.println("is Not inorder\n");
        }
        else
        {
          System.out.println("is inorder\n");
        }
      }
      else
      {
        System.out.println("is Not inorder\n");
      }

    }
    else
    {
      System.out.println("Empty BST\n");
    }
  }
  public void inorder(Node root)
  {
    if(root!=null)
    {

      inorder(root.left);
      inorder(root.right);
      System.out.print("  "+ root.data);
    }
  }
  public static void main(String[] args) 
  {

    BST obj = new BST();

    /*
    Add nodes in binary search tree

               5
             /   \
            3     9
           / \   / \
          2   4 8   11
                   /
                  10

    */                
    obj.add(5); 
    obj.add(3); 
    obj.add(9); 
    obj.add(2); 
    obj.add(4); 
    obj.add(8); 
    obj.add(11); 
    obj.add(10); 

    System.out.print("\n Inorder " );
    obj.inorder(obj.root);
    System.out.println("\n");

    //Test Case
    int []sequence1={2,  3,  4,  5,  8, 9, 10};

    obj.bst_inorder(sequence1);

    int []sequence2={2,  3,  4,  5,   8, 9, 10,  11, 11};

    obj.bst_inorder(sequence2);

    int []sequence3={2,  3,  4,  5, 8, 9, 10,  11};

    obj.bst_inorder(sequence3);
  }
}

Output

 Inorder   2  4  3  8  10  11  9  5


 Sequence : 2  3  4  5  8  9  10  is Not inorder


 Sequence : 2  3  4  5  8  9  10  11  11  is Not inorder


 Sequence : 2  3  4  5  8  9  10  11  is inorder
#Python Program 
#Check if array is inorder of bst
class Node:
  def __init__(self,data):
    self.data=data
    self.left=None
    self.right=None

   
class BST:

  def __init__(self):

    # Assign default value
    self.root=None
    self.counter = 0
  
  #insert  element
  def add(self,data):

    # Create a dynamic node of binary search tree 
    new_node = Node(data)

    if(self.root == None):
      # When adds a first node in binary tree
      self.root = new_node
    
    else:
      find = self.root

      # add new node to proper position
      while(find != None):

        if(find.data >= data): 

          if(find.left==None):

            find.left = new_node
            break
          
          else: 

            # visit left sub-tree
            find = find.left
          
        
        else:

          if(find.right == None):

            find.right = new_node
            break
          
          else:

            # visit right sub-tree
            find = find.right



  def inorder(self, root):
    if(root!=None):
      
      self.inorder(root.left)
      print(root.data, end="  ")
      self.inorder(root.right)
      
    
  #Check if a given sequence is form of BST tree inorder
  def is_bst_inorder( self, root,sequence,size):
    if(root != None):
      
      a = self.is_bst_inorder(root.left,sequence,size)

      if( self.counter < size  and  sequence[self.counter] != root.data) :
        return False
      
      self.counter+=1
      b = self.is_bst_inorder(root.right,sequence,size)
      if (a==False  or  b==False):

        return False
    
    return True

  def bst_inorder(self,sequence):

    if(len(sequence)<0):
      return

    if(self.root!=None):
      
      self.counter=0
      size = len(sequence)
      print("\nSequence : ")

      for i in sequence :
        print(i, end="  ")
      
      if(self.is_bst_inorder(self.root,sequence,size)):

        if(self.counter!=size):

          print("Is Not inorder")
        
        else:
          print("Is inorder")
        
      
      else:
        print("Is Not inorder")
    
     
    
    else:
      print("Empty BST\n")
    


def main():

  obj = BST()


  #  Add nodes in binary search tree
  #  
  #             5
  #           /   \
  #          3     9
  #         / \   / \
  #        2   4 8   11
  #                 /
  #                10   
  #       

  obj.add(5); 
  obj.add(3); 
  obj.add(9); 
  obj.add(2); 
  obj.add(4); 
  obj.add(8); 
  obj.add(11); 
  obj.add(10); 

  print("\nInorder " )
  obj.inorder(obj.root)
  print()

  #Test Case
  sequence1=[2,  3,  4,  5,  8, 9, 10]

  obj.bst_inorder(sequence1)

  sequence2=[2,  3,  4,  5,   8, 9, 10,  11, 11]

  obj.bst_inorder(sequence2)

  sequence3=[2,  3,  4,  5, 8, 9, 10,  11]

  obj.bst_inorder(sequence3)

if __name__ =="__main__":
  main()

Output

Inorder 
2  3  4  5  8  9  10  11  

Sequence : 
2  3  4  5  8  9  10  Is Not inorder

Sequence : 
2  3  4  5  8  9  10  11  11  Is Not inorder

Sequence : 
2  3  4  5  8  9  10  11  Is inorder
//C# program
//Check if array is inorder of bst
using System;
public class Node
{
  public int data;
  public Node left,right;
}
public class BST
{


  public Node root;
  static int counter;

  //Class constructors
  BST()
  {
    root=null;
    counter=0;
  } 

  //insert  element
  public void add(int data)
  {
    //Create a dynamic node of binary search tree 
    Node new_node = new 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;

      if(root == null)
      {
        //When adds a first node in binary tree
        root = new_node;
      }
      else
      {
        Node find = root;

        //add new node to proper position
        while(find != null)
        {
          if(find.data >= data)
          { 
            if(find.left==null)
            {
              find.left = new_node;
              break;
            }
            else
            { 
              //visit left sub-tree
              find = find.left;
            }
          }
          else
          {
            if(find.right == null)
            {
              find.right = new_node;
              break;
            }
            else
            {
              //visit right sub-tree
              find = find.right;
            }
          }
        }
      }
    }
    else
    {
      Console.WriteLine("Memory Overflow");
    }
  }

  //Check if a given sequence is form of BST tree inorder
  public Boolean is_bst_inorder( Node root,int []sequence,int size)
  {
    if(root != null)
    {

      Boolean a = is_bst_inorder(root.left,sequence,size);

      if( counter < size && sequence[ counter] != root.data) 
      {
        return false;
      }
      counter++;
      Boolean b = is_bst_inorder(root.right,sequence,size);
      if (a==false || b==false)
      {
        return false;
      }
    }
    return true;
  }
  public void bst_inorder(int []sequence)
  {
    if(sequence.Length<0)
    {
      return;
    }

    if(root!=null)
    {

      counter=0;
      int size = sequence.Length;
      Console.Write("\n Sequence : ");
      for (int i = 0; i < size; ++i)
      {
        Console.Write(sequence[i]+ "  ");
      }
      if(is_bst_inorder(root,sequence,size))
      {
        if(counter!=size)
        {
          Console.WriteLine("is Not inorder\n");
        }
        else
        {
          Console.WriteLine("is inorder\n");
        }
      }
      else
      {
        Console.WriteLine("is Not inorder\n");
      }

    }
    else
    {
      Console.WriteLine("Empty BST\n");
    }
  }
  public void inorder(Node root)
  {
    if(root!=null)
    {

      inorder(root.left);
      inorder(root.right);
      Console.Write("  "+ root.data);
    }
  }
  public static void Main(String[] args) 
  {

    BST obj = new BST();

    /*
    Add nodes in binary search tree

               5
             /   \
            3     9
           / \   / \
          2   4 8   11
                   /
                  10

    */                
    obj.add(5); 
    obj.add(3); 
    obj.add(9); 
    obj.add(2); 
    obj.add(4); 
    obj.add(8); 
    obj.add(11); 
    obj.add(10); 

    Console.Write("\n Inorder " );
    obj.inorder(obj.root);
    Console.WriteLine("\n");

    //Test Case
    int []sequence1={2,  3,  4,  5,  8, 9, 10};

    obj.bst_inorder(sequence1);

    int []sequence2={2,  3,  4,  5,   8, 9, 10,  11, 11};

    obj.bst_inorder(sequence2);

    int []sequence3={2,  3,  4,  5, 8, 9, 10,  11};

    obj.bst_inorder(sequence3);
  }
}

Output

Inorder   2  4  3  8  10  11  9  5


 Sequence : 2  3  4  5  8  9  10  is Not inorder


 Sequence : 2  3  4  5  8  9  10  11  11  is Not inorder


 Sequence : 2  3  4  5  8  9  10  11  is inorder
<?php
//Php program 
//Check if array is inorder of bst
class Node
{
  public $data;
  public $left;
  public $right;
  function __construct($data)
  {
    $this->data = $data;
    $this->length = NULL;
    $this->right = NULL;
  }
}
class BST
{

  public $root;
  function __construct()
  {
    $root=NULL;
  }

 //Adding a new node in binary search tree
  function add($data)
  {
    //Create a dynamic node of binary search tree 
    $new_node = new Node($data);

    if($this->root == NULL)
    {
      //When adds a first node in binary tree
      $this->root = $new_node;
    }
    else
    {
      $find = $this->root;

      //add new node to proper position
      while($find != NULL)
      {
        if($find->data >= $data)
        { 
          if($find->left==NULL)
          {
            $find->left = $new_node;
            break;
          }
          else
          { 
          //visit left sub-tree
            $find = $find->left;
          }
        }
        else
        {
          if($find->right == NULL)
          {
            $find->right = $new_node;
            break;
          }
          else
          {
          //visit right sub-tree
            $find = $find->right;
          }
        }
      }
    }

  }

//Check if a given sequence is form of BST tree inorder
function is_bst_inorder($root,$sequence,&$counter,$size)
{
  if($root != NULL)
  {
      
    $a = $this->is_bst_inorder($root->left,$sequence,$counter,$size); 
    

    if($counter < $size && $sequence[$counter] != $root->data || $a == false ) 
    {
   
      return flase;
    }
    $counter++;
 
    $b = $this->is_bst_inorder($root->right,$sequence,$counter,$size);
    if($b==false || $counter > $size)
    {
      return false;
    }
  }
  return true;
}
function bst_inorder($sequence)
{
  $size=count($sequence);
  if($size<0) return;

  if($this->root!=NULL)
  {
    
    $counter=0;
    echo ("\n Sequence : ");
    for ($i = 0; $i < $size; ++$i)
    {
      echo $sequence[$i]."  ";
    }
    if($this->is_bst_inorder($this->root,$sequence,$counter,$size))
    {
      if($counter!=$size)
      {
        echo ("is Not inorder\n");
      }
      else
      {
        echo ("is inorder\n");
      }
    }
    else
    {
       echo ("is Not inorder\n");
    }
   
  }
  else
  {
    echo ("Empty BST\n");
  }
}
  function inorder($root)
  {
    if($root!=NULL)
    {
      
      $this->inorder($root->left);
      echo "  ". $root->data;
      $this->inorder($root->right);
      
    }
  }
}
function main()
{
  //Make a object of BST class
  $obj= new BST();


  //Add nodes in binary search tree
  /*
             5
           /   \
          3     9
         / \   / \
        2   4 8   11
                 /
                10   
  */                  

  $obj->add(5); 
  $obj->add(3); 
  $obj->add(9); 
  $obj->add(2); 
  $obj->add(4); 
  $obj->add(8); 
  $obj->add(11); 
  $obj->add(10); 

  echo ("\n Inorder " );
  $obj->inorder($obj->root);
  echo ("\n");

  //Test Case
  $sequence1=array(2,  3,  4,  5,  8, 9, 10);

  $obj->bst_inorder($sequence1);

  $sequence2=array(2,  3,  4,  5,   8, 9, 10,  11, 11);

  $obj->bst_inorder($sequence2);

  $sequence3=array(2,  3,  4,  5, 8, 9, 10,  11);

  $obj->bst_inorder($sequence3);
}
main();
?>

Output

 Inorder   2  3  4  5  8  9  10  11

 Sequence : 2  3  4  5  8  9  10  is Not inorder

 Sequence : 2  3  4  5  8  9  10  11  11  is Not inorder

 Sequence : 2  3  4  5  8  9  10  11  is inorder


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