Do you think IIT Guwahati certified course can help you in your career?
No
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.
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
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"
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.
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
Then it goes to 12 and then 13. Increase the index because it is the current element in the series once again.
Then it goes to 17 and then 18. Increase the index because element 18 is now present in the sequence.
Finally, it stops around number 20.
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
/*
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).
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.