Check if given sorted sub | C ++ program to find if given array exists as a subsequece in BST ; A binary Tree node ; A utility function to create a new BST node with key as given num ; A utility function to insert a given key to BST ; function to check if given sorted sub - sequence exist in BST index -- > iterator for given sorted sub - sequence seq [ ] -- > given sorted sub - sequence ; We traverse left subtree first in Inorder ; If current node matches with se [ index ] then move forward in sub - sequence ; We traverse left subtree in the end in Inorder ; A wrapper over seqExistUtil . It returns true if seq [ 0. . n - 1 ] exists in tree . ; Initialize index in seq [ ] ; Do an inorder traversal and find if all elements of seq [ ] were present ; index would become n if all elements of seq [ ] were present ; driver program to run the case
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; struct Node * left , * right ; } ; struct Node * newNode ( int num ) { struct Node * temp = new Node ; temp -> data = num ; temp -> left = temp -> right = NULL ; return temp ; } struct Node * insert ( struct Node * root , int key ) { if ( root == NULL ) return newNode ( key ) ; if ( root -> data > key ) root -> left = insert ( root -> left , key ) ; else root -> right = insert ( root -> right , key ) ; return root ; } void seqExistUtil ( struct Node * ptr , int seq [ ] , int & index ) { if ( ptr == NULL ) return ; seqExistUtil ( ptr -> left , seq , index ) ; if ( ptr -> data == seq [ index ] ) index ++ ; seqExistUtil ( ptr -> right , seq , index ) ; } bool seqExist ( struct Node * root , int seq [ ] , int n ) { int index = 0 ; seqExistUtil ( root , seq , index ) ; return ( index == n ) ; } int main ( ) { struct Node * root = NULL ; root = insert ( root , 8 ) ; root = insert ( root , 10 ) ; root = insert ( root , 3 ) ; root = insert ( root , 6 ) ; root = insert ( root , 1 ) ; root = insert ( root , 4 ) ; root = insert ( root , 7 ) ; root = insert ( root , 14 ) ; root = insert ( root , 13 ) ; int seq [ ] = { 4 , 6 , 8 , 14 } ; int n = sizeof ( seq ) / sizeof ( seq [ 0 ] ) ; seqExist ( root , seq , n ) ? cout << " Yes " : cout << " No " ; return 0 ; }