QUESTION

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.\n\n200px-Binary_search_tree.svg\n\nExamples:\n\n// For binary search tree\nInput : seq[] = {4, 6, 8, 14}\nOutput: \”Yes\”\n\nInput : seq[] = {1, 2, 3, 8}\nOutput: \”No\”

ANSWER

#include<bits/stdc++.h>
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;
}