#include <bits/stdc++.h>
using namespace std;

// tree node is defined
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int data)
    {
        val = data;
        left = NULL;
        right = NULL;
    }
};

// inorder traversal to check if the given 
// sorted subsequence exists in the BST
void DoesSeqExistRec(TreeNode* root, vector<int> sequence, int& index)
{
    //base case
    if (!root)
        return;

    // traverse left subtree first as it's inorder traversal
    DoesSeqExistRec(root->left, sequence, index);

    // If current node matches with current sequence 
    // element(sequence[index]) then move
    // to the next element in the sequenece
    if (root->val == sequence[index])
        index++;

    // traverse right subtree
    DoesSeqExistRec(root->right, sequence, index);
}

// function to check whether the sequence exists or not
bool DoesSeqExist(TreeNode* root, vector<int> sequence)
{

    int index = 0;

    // recursive function to check if all elements 
    // of the sequence are in the BST or not
    DoesSeqExistRec(root, sequence, index);

    //if after the inorder traversal as we have discussed, 
    //index reaches towards the end
    //then the BST contains the sequence other wise not
    if (index == sequence.size())
        return true;
    else
        return false;
}

int main()
{
    TreeNode* root = new TreeNode(16);
    
    root->left = new TreeNode(3);
    root->left->right = new TreeNode(13);
    root->left->right->left = new TreeNode(10);
    root->left->right->left->left = new TreeNode(7);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(18);

    vector<int> sequence1{ 7, 13, 18, 20 };

    if (DoesSeqExist(root, sequence1))
        cout << "Yes the sequence exists in the binary search tree\n";
    else
        cout << "No, the sequence exists in the binary search tree";

    vector<int> sequence2{ 7, 13, 14, 20 };

    if (DoesSeqExist(root, sequence2))
        cout << "Yes the sequence exists in the binary search tree\n";
    else
        cout << "No, the sequence doesn't exist in the binary search tree";

    return 0;
}