Table of contents
1.
Introduction👨‍🏫
2.
Problem Statement
2.1.
Sample Examples 
3.
Simple solution
4.
Efficient Solution
4.1.
Steps of Algorithm 
4.2.
Implementation in C++
4.3.
Implementation in Java
4.4.
Implementation in Python
4.5.
Complexity Analysis
5.
Frequently Asked Questions
5.1.
What do you understand from the term Binary Search Tree?
5.2.
How many maximum children can each Binary Search Tree node have?
5.3.
What property must every child node have to follow in a Binary Search Tree?
5.4.
What is the difference between a binary tree and a binary search tree?
5.5.
What is inorder traversal? 
6.
Conclusion 
Last Updated: Mar 27, 2024
Medium

Check if the given sorted sub-sequence exists in BST

Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction👨‍🏫

When we are talking about data structures, we cannot forget the name Tree. The tree is an essential Data Structure, helpful in hierarchically storing data. 

Check if the given sorted sub-sequence exists in BST

 

A binary search tree which is a rooted binary tree, satisfies the binary search property. The nodes are organized in total order, the nodes with keys larger than any given node are stored on the right subtrees, and the nodes with keys equal to or less than are put on the left subtrees.

This article will discuss the Binary Search Tree and its properties. So let's start to enhance our knowledge about Binary Search Trees.

Problem Statement

The problem states that check if the given sorted subsequence exits in the Binary Search Tree or Not. We are aware that a Binary search tree's in-order traversal results in a sorted list of the keys. This fact allows us to determine whether or not a specific sorted subsequence is present in the Binary Search Tree.

Sample Examples 

tree

For the above binary search tree

Input: Sequence1[] = {9, 13, 18, 20}

Output: "Yes the first sequence exists in the binary search tree"

Input: Sequence2[] = {9, 13, 14, 20}

Output: "No, the second sequence doesn't exist in the binary search tree"

Simple solution

Prerequisite: Binary Search Trees

One easy way to determine whether a sub-sequence is present in BST or not is to record inorder traversal in an auxiliary array and then compare each element of the sorted sub-sequence with the inorder traversal of the tree one by one. This method's time complexity is O(n), however the additional storage space needed for array traversal is O(n).

Efficient Solution

Let’s say, we have given two sequences to check where they exist or not.

Sequence 1: [9, 13, 18, 20]

Sequence 2: [9, 13, 14, 20]

We already know that a sorted list is produced by an in-order traverse of a binary search tree. Therefore, we can make use of that fact to sort the list and then just search for each element of the sequence one at a time, which is linear in execution time but requires more storage. So without storing the inorder traversal, we can check the sequence elements one by one while doing the in-order traversal.

The concept is to hold an index pointer to the first element of the sequence and increment the index pointer as we find that indexed element during the inorder traverse. The complete sequence is in the Binary search tree if, after doing the inorder traverse, we discover that the index pointer has reached the end of the sequence; otherwise, it is not.

coding img

Steps of Algorithm 

Thus, the input BST is identical to that of the example, and the sequence is [9, 13, 18, 20].

  • So the inorder traversal begins from the root and the first node visited is 5 and then it visits 9 which is the first element of the sequence too. So increment the index
BST img
  • Then it goes to 12 and then 13. Increase the index because it is the current element in the series once again.
BST img
  • Then it goes to 17 and then 18. Increase the index because element 18 is now present in the sequence.
BST img
  • Finally, it stops around number 20.
BST img

 

  • The sequence is therefore present in the database because the index pointer reaches the end of it after the inorder traversal is complete.
     

For Sequence2, when the index pointer reaches at 14, it doesn't get incremented further since 14 isn't found in the BST. Here we find that the index pointer has not reached the end of the sequence so it is not the sub-sequence of the BST.

Implementation in C++

Now let’s see the implementation of the above problem in C++. 
 

#include <bits/stdc++.h>


using namespace std;


// Defining the tree node
class TreeNode {
  public:
    int v;
  TreeNode * left;
  TreeNode * right;
  TreeNode(int value) {
    v = value;
    left = NULL;
    right = NULL;
  }
};


/* 
Using inorder traversal to whether the given sorted 
subsequence exists or not in the binary search tree.
*/
void CheckSeqExistrec(TreeNode * root, vector < int > sequence, int & index) {
  //Base case
  if (!root)
    return;


  // As it's inorder traversal Traverse left subtree first 
  CheckSeqExistrec(root -> left, sequence, index);


  /* 
  If the current node matches with the current 
  sequence[index] then move to the next element in the sequence
  */
  if (root -> v == sequence[index])
    index++;


  // Traverse the right subtree
  CheckSeqExistrec(root -> right, sequence, index);
}


// Function to check if the sequence exists or not
bool CheckSeqExist(TreeNode * root, vector < int > sequence) {


  int index = 0;


  /*
  Recursive function for checking if all 
  elements of the sequence are in the BST
  */
  CheckSeqExistrec(root, sequence, index);


  /*
  If after the inorder traversal index reaches towards 
  the end then only the BST contains the sequence other wise not.
  */
  if (index == sequence.size())
    return true;
  else
    return false;
}


int main() {
  TreeNode * root = new TreeNode(17);


  root -> left = new TreeNode(5);
  root -> left -> right = new TreeNode(13);
  root -> left -> right -> left = new TreeNode(12);
  root -> left -> right -> left -> left = new TreeNode(9);
  root -> right = new TreeNode(20);
  root -> right -> left = new TreeNode(18);


  vector < int > Sequence1 { 9, 13, 18, 20};


  if (CheckSeqExist(root, Sequence1))
    cout << "Yes the first sequence exists in the binary search tree\n";
  else
    cout << "No, the first sequence exists in the binary search tree";


  vector < int > Sequence2 { 9, 13, 14, 20  };


  if (CheckSeqExist(root, Sequence2))
    cout << "Yes the second sequence exists in the binary search tree\n";
  else
    cout << "No, the second sequence doesn't exist in the binary search tree";
  return 0;
}
You can also try this code with Online C++ Compiler
Run Code

Output:

Implementation in Java

/* 
Java program to check if given 
sorted sub-sequence exists in BST
*/
import java.util.*;


class Main {


  // A binary tree node


  static class Node {
    int value;
    Node left, right;
  };


  //Structure of int class


  static class ABC {
    int a;
  }


  // A utility function to create a new node with key as given num


  static Node NewNode(int num) {
    Node temp = new Node();
    temp.value = num;
    temp.left = temp.right = null;
    return temp;
  }


  // A utility function to insert a given key to BST


  static Node insert(Node root, int key) {
    if (root == null)
      return NewNode(key);
    if (root.value > key)
      root.left = insert(root.left, key);
    else
      root.right = insert(root.right, key);
    return root;
  }


  /* Function to check if given sorted sub-sequence 
  exist in BST index - iterator for given sorted sub-sequence 
  */
  //seq[], given sorted sub-sequence
  static void SeqExistUtil(Node ptr, int seq[], ABC index) {
    if (ptr == null)
      return;


    /* 
    We traverse left subtree
    first in Inorder
    */
    SeqExistUtil(ptr.left, seq, index);


    // If current node matches with seq[index] then move forward in sub-sequence


    if (ptr.value == seq[index.a])
      index.a++;


    // Traverse left subtree in the end in Inorder


    SeqExistUtil(ptr.right, seq, index);
  }


  /* 
  A wrapper over SeqExistUtil.
  if seq[0..n-1] exists in tree it returns true. 
  */

  static boolean SeqExist(Node root, int seq[], int n) {
    // Initialize index in seq[]
    ABC index = new ABC();
    index.a = 0;
    /*
    Do an inorder traversal and see 
    if all elements of seq[] are present 
    */
    SeqExistUtil(root, seq, index);

    // Index will become n if all elements of seq[] are present

    return (index.a == n);
  }

  // Driver code
  public static void main(String args[]) {
    Node root = null;
    root = insert(root, 17);
    root = insert(root, 5);
    root = insert(root, 13);
    root = insert(root, 12);
    root = insert(root, 9);
    root = insert(root, 20);
    root = insert(root, 18);

    int seq[] = {
      9,
      13,
      14,
      40
    };
    int n = seq.length;

    if (SeqExist(root, seq, n))
      System.out.println("Yes, the sequence exists in the binary search tree");
    else
      System.out.println("No, the sequence does not exists in the binary search tree");
  }
}

 

Output:

Implementation in Python

# Python3 program to Check if given 
# sorted sub-sequence exists in BST
class Node:

# Constructor to create a new node
	def __init__(self, d):
		self.d = d
		self.left = None
		self.right = None
		
# Utility function to insert a
# given key to BST
def insert(root, key):
	if root == None:
		return Node(key)
	if root.d > key:
		root.left = insert(root.left, key)
	else:
		root.right = insert(root.right, key)
	return root

# Function to see if given sorted
# sub-sequence exist in BST index or not.
# Iterator for given sorted sub-sequence
# seq[], given sorted sub-sequence
def seqExistu(ptr, seq, index):
	if ptr == None:
		return

	# Traverse the left subtree
	# First in Inorder
	seqExistu(ptr.left, seq, index)

	# If the current node matches with the seq[index[0]]
	# then move forward in sub-sequence
	if ptr.d == seq[index[0]]:
		index[0] += 1

	# We traverse left subtree in
	# the end in Inorder
	seqExistu(ptr.right, seq, index)

# A wrapper over seqExistu. It will return
# true if the seq[0..n-1] exists in tree.
def SeqExist(root, seq, n):
	
	# Initialize index in seq[]
	index = [0]

	# Do an inorder traversal and find if
	# all elements of seq[] were present
	seqExistu(root, seq, index)

	# Index would become n if all elements
	# of seq[] were present
	if index[0] == n:
		return True
	else:
		return False

# Driver Code
if __name__ == '__main__':
	root = None
	root = insert(root, 17)
	root = insert(root, 5)
	root = insert(root, 13)
	root = insert(root, 12)
	root = insert(root, 9)
	root = insert(root, 20)
	root = insert(root, 18)

	seq = [9, 13, 18, 20]
	n = len(seq)
	if SeqExist(root, seq, n):
		print("Yes, the sequence exists in the binary search tree")
	else:
		print("No, the sequence does not exists in the binary search tree")

Output:

Complexity Analysis

Time Complexity: O(N)

We are only doing linear traversal of the arrays, so time complexity is linear to find the minimum number of swaps to convert binary tree to binary search tree. 

Space Complexity: O(N)

We are creating a temporary array to store the in-order traversal of the given tree, so space complexity is O(N). 


Check out this array problem - Merge 2 Sorted Arrays

Frequently Asked Questions

What do you understand from the term Binary Search Tree?

A binary Search Tree is a classification of Trees in which every node in the tree can have at most two children, the left child, and the right child. The data of the right child and the left child must be greater and smaller than the data of the parent node, respectively.

How many maximum children can each Binary Search Tree node have?

The Binary Search Tree node can have a maximum of two children. The children are called left and right children. 

What property must every child node have to follow in a Binary Search Tree?

The property that every child node has to follow is that if it is a left child, its value should be smaller than the parent node, and if it is a right child, its value should be greater than the parent node.

What is the difference between a binary tree and a binary search tree?

A tree that has a maximum of 2 children is called a binary tree, whereas a binary search tree is a particular binary tree having the following properties. 

Keys in the left subtree are always smaller than the root's node, whereas keys in the right subtree are greater than the root's node. 

What is inorder traversal? 

In order traversal, we first traverse the left subtree, visit the root, and traverse the right subtree. 

Conclusion 

In this article, we discussed a very interesting problem in which we have to check if a given sorted sub-sequence exists in a binary search tree Hope you have understood the solution approach. 

 

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem DesignMachine learning, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Happy Learning!!

Live masterclass