Binary Search tree

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;
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro