Check if given sorted sub-sequence exists in binary search tree - GeeksforGeeks

Check if given sorted sub-sequence exists in binary search tree - GeeksforGeeks
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.

A simple solution is to store inorder traversal in an auxiliary array and then by matching elements of sorted sub-sequence one by one with inorder traversal of tree , we can if sub-sequence exist in BST or not. Time complexity for this approach will be O(n) but it requires extra space O(n) for storing traversal in an array.

An efficient solution is to match elements of sub-sequence while we are traversing BST in inorder fashion. We take index as a iterator for given sorted sub-sequence and start inorder traversal of given bst, if current node matches with seq[index] then move index in forward direction by incrementing 1 and after complete traversal of BST if index==n that means all elements of given sub-sequence have been matched and exist as a sorted sub-sequence in given BST.

void seqExistUtil(struct Node *ptr, int seq[], int &index)

{

    if (ptr == NULL)

        return;

 

    // We traverse left subtree first in Inorder

    seqExistUtil(ptr->left, seq, index);

 

    // If current node matches with se[index] then move

    // forward in sub-sequence

    if (ptr->data == seq[index])

        index++;

 

    // We traverse left subtree in the end in Inorder

    seqExistUtil(ptr->right, seq, index);

}

 

// A wrapper over seqExistUtil. It returns true

// if seq[0..n-1] exists in tree.

bool seqExist(struct Node *root, int seq[], int n)

{

    // Initialize index in seq[]

    int index = 0;

 

    // Do an inorder traversal and find if all

    // elements of seq[] were present

    seqExistUtil(root, seq, index);

 

    // index would become n if all elements of

    // seq[] were present

    return (index == n);

}

Read full article from Check if given sorted sub-sequence exists in binary search tree - GeeksforGeeks