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.

// For above binary search tree

Input : seq[] = {4, 6, 8, 14}
Output: "Yes"

Input : seq[] = {1, 2, 3, 8}
Output: "No"

We can store the inorder traversal in an auxiliary array and then by matching elements of sorted sub-sequence one by one with inorder traversal of tree. Time complexity for this approach will be O(n) but it requires extra space O(n) for storing traversal in an array.

We can improve this approach by matching elements of sub-sequence while we are traversing BST in inorder fashion. We take index as an iterator for given sequence and start doing inorder traversal. If we find a match, we increase the index value by one. After complete traversal, we check if index is equal to the size of the sequence.

void BinarySearchTree::subSequenceExistUtil(TreeNode *root, vector<int> seq, int &index) {
    if (!root) return;

    subSequenceExistUtil(root->left, seq, index);

    if (seq[index] == root->val) {
        index += 1;
    }

    subSequenceExistUtil(root->right, seq, index);
}

// Check if sub sequence exist
bool BinarySearchTree::subSequenceExist(TreeNode *root, vector<int> seq) {
    if (seq.empty()) { return true; }

    int index = 0;
    subSequenceExistUtil(root, seq, index);
    return index == seq.size();
}