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;
}