PROGRAM TO CHECK IF GIVEN SORTED SUB-SEQUENCE EXISTS IN BINARY SEARCH TREE














































PROGRAM TO CHECK IF GIVEN SORTED SUB-SEQUENCE EXISTS IN BINARY SEARCH TREE



Description-
  

  Binary search tree-  It is a binary tree which is  a node based data structure where every node 

                                           has the following properties.

             

                        -> The left sub-tree of every node consists of keys less than the node's key.

                        -> The right sub-tree of every node consists of keys greater than the node's key.

                        ->Right sub-tree and left sub-tree must also be a binary tree.

                                 ->There are no duplicate elements in the tree.
   The main reason for switching from linked lists to trees is to have an efficient search method. In linked lists the   order  of  search is O(n) which can be reduced to O(log n) in binary search trees.

    program description-

    In this program we are given a Binary Search tree and a sorted sub sequence.
    ex-   
                                                            
200px-Binary_search_tree.svg

                      

 Example sequences for above binary tree-
          input- int seq[]={1,6,11,13}
          output-"Exists";
          input-int seq[]={4,14,20}
          output-"Does not exists";
   
          
   Approach  -
1)   As  the sequence is in sorted order the simple solution is to store the in-order traversal in an  array
      (as in-order traversal of a binary search tree is in sorted order) and compare the elements in seq array.
       If we proceed in this way there will be 3 cases.
       ->If the  element in auxiliary array matches the number in the sequence  then go to the next                       number in   sequence array.
     -> If the element in the auxiliary array is smaller than the  number in sequence move forward until              you find the exact match or element greater than the required number .
     ->If element is greater than  the required number that means the required number is not                           present in the sub-sequence.
 This approach takes O(n) time and also O(n) space in order to store the elements in Binary search tree
2)   The efficient way to  solve this is to check whether the elements are present or not while traversing in IN-ORDER.take an iterator which points to the first element of sequence initially and whenever element is found while traversing simply   increment the iterator.If the Iterator reaches the
end of seq after the traversal that means the sub-sequence is present in binary search tree else it is not present.


-----------------------------------------------------------------------------------------------------------------------------------------------
c++ code for the above program

#include<iostream> #include<cstdlib> #include<vector> #include<string> using namespace std; template<class T> class binarysearchtree{ private: struct node{ int data; struct node *llink,*rlink; };node *root; public: binarysearchtree(){ root=NULL; } void insert(T ); string search(vector <T> ); void inorder(node * ,vector <T> ,int &); }; template<class T> void binarysearchtree<T>::insert(T d){ node *temp=new node; temp->data=d; temp->llink=NULL; temp->rlink=NULL; if(root==NULL) root=temp; else { node *cur=root,*parent; while(cur!=NULL){ parent=cur; if(cur->data>d) cur=cur->llink; else cur=cur->rlink; } if(parent->data>d) parent->llink=temp; else parent->rlink=temp; } } template<class T> void binarysearchtree<T>::inorder(node *p,vector <T> seq,int &iter){ if(p==NULL || iter==seq.size()) return ; inorder(p->llink,seq,iter); if(p->data==seq[iter]) iter++; inorder(p->rlink,seq,iter); } template <class T> string binarysearchtree<T>::search(vector<T> seq){ int iter=0; inorder(root,seq,iter); if(iter==seq.size()) return "Exists"; else return "Des not exists"; } int main(){ binarysearchtree <int> b; b.insert(8); b.insert(10); b.insert(3); b.insert(14); b.insert(1); b.insert(6); b.insert(4); b.insert(7); b.insert(13); binarysearchtree <char> c; c.insert('m'); c.insert('h'); c.insert('f'); c.insert('g'); c.insert('o'); c.insert('n'); c.insert('w'); c.insert('s'); c.insert('y'); vector <int> seq1={4,14,20}; vector<int> seq2={1,6,7,13}; vector<char> seq3={'f','s','w','r'}; cout<<"seq1 "<<b.search(seq1)<<endl; cout<<"seq2 "<<b.search(seq2)<<endl; cout<<"seq3 "<<c.search(seq3)<<endl; return 0; }
Result
$g++ -o main *.cpp
$main
seq1 Des not exists seq2 Exists seq3 Des not exists



More Articles of PRIYANKA S:

Name Views Likes
PROGRAM TO CHECK IF GIVEN SORTED SUB-SEQUENCE EXISTS IN BINARY SEARCH TREE 124 0

Comments