 ### C++ program to find check if given sorted sub-sequence exists in binary search tree

Given a binary search tree and a sorted sub-sequence. the task is to check if the given sorted sub-sequence exist in binary search tree or not. An efficient solution is to match elements of sub-sequence while we are traversing BST in inorder fashion. We take index as a iterator for given sorted sub-sequence and start inorder traversal of given bst, if current node matches with seq[index] then move index in forward direction by incrementing 1 and after complete traversal of BST if index==n that means all elements of given sub-sequence have been matched and exist as a sorted sub-sequence in given BST.

// C++ program to find if given array exists as a
// subsequece in BST
#include<bits/stdc++.h>
using namespace std;

// A binary Tree node
struct Node
int data;
struct Node *left, *right;
};

// A utility function to create a new BST node
// with key as given num
struct Node* newNode(int num)
struct Node* temp = new Node;
temp->data = num;
temp->left = temp->right = NULL;
return temp;

// A utility function to insert a given key to BST
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;

// function to check if given sorted sub-sequence exist in BST
// index --> iterator for given sorted sub-sequence
// seq[] --> given sorted sub-sequence
void seqExistUtil(struct Node *ptr, int seq[], int &index)
if (ptr == NULL)
return;

// We traverse left subtree first in Inorder
seqExistUtil(ptr->left, seq, index);

// If current node matches with se[index] then move
// forward in sub-sequence
if (ptr->data == seq[index])
index++;

// We traverse left subtree in the end in Inorder
seqExistUtil(ptr->right, seq, index);

// A wrapper over seqExistUtil. It returns true
// if seq[0..n-1] exists in tree.
bool seqExist(struct Node *root, int seq[], int n)
// Initialize index in seq[]
int index = 0;

// Do an inorder traversal and find if all
// elements of seq[] were present
seqExistUtil(root, seq, index);

// index would become n if all elements of
// seq[] were present
return (index == n);

// driver program to run the case
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);

seqExist(root, seq, n)? cout << "Yes" :
cout << "No";

return 0;

Output:
`Yes` 