Check if a sorted sub sequence is part of BST
Here given code implementation process.
//C Program
//Check if given sorted sub-sequence exists in binary search tree
#include <stdio.h>
#include <stdlib.h>
//structure of Binary Search Tree node
struct Node
{
int data;
struct Node *left,*right;
};
//Adding a new node in binary search tree
void add( struct Node **root, int data)
{
//Create a dynamic node of binary search tree
struct Node *new_node = (struct Node *)malloc(sizeof(struct Node ));
if(new_node!=NULL)
{
//Set data and pointer values
new_node->data = data;
new_node->left = NULL; //Initially node left-pointer is NULL
new_node->right = NULL;//Initially node right-pointer is NULL
if(*root == NULL)
{
//When adds a first node in binary tree
*root = new_node;
}
else
{
struct Node *find = *root;
//iterate binary tree and add new node to proper position
while(find != NULL)
{
if(find -> data > data)
{
if(find->left==NULL)
{
find->left = new_node;
break;
}
else
{ //visit left sub-tree
find = find->left;
}
}
else
{
if(find->right == NULL)
{
find->right = new_node;
break;
}
else
{
//visit right sub-tree
find = find->right;
}
}
}
}
}else
{
printf("Memory Overflow\n");
exit(0); //Terminate program execution
}
}
void compare_element(struct Node*root,int *index,int sequence[])
{
if(root!=NULL)
{
compare_element(root->left,index,sequence);
if(root->data==sequence[*index])
{
(*index)++;
}
compare_element(root->right,index,sequence);
}
}
void display(int sequence[],int size)
{
for (int i = 0; i < size; ++i)
{
printf(" %d",sequence[i]);
}
}
void check_sequence(struct Node*root,int sequence[],int size)
{
if(size<=0)
{
//invalid sequence size
return;
}
else if(root != NULL )
{
int index=0;
compare_element(root,&index,sequence);
if(index<size)
{
printf("\nSequence Are Not Exist : ");
}
else
{
printf("\nSequence Are Exist : ");
}
display(sequence,size);
}
else
{
printf("\n Empty Tree\n");
}
}
void inorder(struct Node*root)
{
if(root!=NULL)
{
inorder(root->left);
printf("%3d ",root->data );
inorder(root->right);
}
}
int main(){
struct Node*root = NULL;
//Add nodes in binary search tree
/*
6
/ \
/ \
3 9
/ \ /
1 5 7
inorder = 1,3,5,6,7,9
*/
add(&root,6);
add(&root,3);
add(&root,9);
add(&root,1);
add(&root,5);
add(&root,7);
inorder(root);
int sequence1[]={1,6,7};
int size = sizeof(sequence1) / sizeof(sequence1[0]);
check_sequence(root,sequence1,size);
int sequence2[]={1,6,7,11};
size = sizeof(sequence2) / sizeof(sequence2[0]);
check_sequence(root,sequence2,size);
return 0;
}
Output
1 3 5 6 7 9
Sequence Are Exist : 1 6 7
Sequence Are Not Exist : 1 6 7 11/*
C++ Program
Check if given sorted sub-sequence exists in binary search tree
*/
#include<iostream>
using namespace std;
class Node {
public:
int data;
Node *left;
Node *right;
Node(int value) {
this->data = value;
this->left = NULL;
this->right = NULL;
}
};
class BinarySearchTree {
public:
Node *root;
int location;
BinarySearchTree() {
this->root = NULL;
this->location = 0;
}
void add(int value) {
Node *new_node = new Node(value);
if (new_node != NULL) {
if (this->root == NULL) {
this->root = new_node;
} else {
Node *find = this->root;
while (find != NULL) {
if (find->data >= value) {
if (find->left == NULL) {
find->left = new_node;
break;;
} else {
find = find->left;
}
} else {
if (find->right == NULL) {
find->right = new_node;
break;;
} else {
find = find->right;
}
}
}
}
} else {
cout << "\nMemory Overflow\n";
}
}
void inorder(Node *head) {
if (head != NULL) {
this->inorder(head->left);
cout << head->data << " ";
this->inorder(head->right);
}
}
void compare_element(Node *head, int sequence[], int size) {
if (head != NULL) {
this->compare_element(head->left, sequence, size);
if (this->location < size && head->data == sequence[this->location]) {
this->location++;
}
this->compare_element(head->right, sequence, size);
}
}
void display(int sequence[], int size) {
int i = 0;
while (i < size) {
cout << " " << sequence[i];
i++;
}
}
void check_sequence(int sequence[], int size) {
if (size <= 0) {
return;
} else
if (this->root != NULL) {
this->location = 0;
this->compare_element(this->root, sequence, size);
if (this->location < size) {
cout << "\nSequence Are Not Exist : ";
} else {
cout << "\nSequence Are Exist : ";
}
this->display(sequence, size);
} else {
cout << "\n Empty Tree\n";
}
}
};
int main() {
BinarySearchTree obj;
/*
6
/ \
/ \
3 9
/ \ /
1 5 7
inorder = 1,3,5,6,7,9
*/
obj.add(6);
obj.add(3);
obj.add(9);
obj.add(1);
obj.add(5);
obj.add(7);
obj.inorder(obj.root);
int sequence1[] = {
1,
6,
7
};
int size = sizeof(sequence1)/sizeof(sequence1[0]);
obj.check_sequence(sequence1, size);
int sequence2[] = {
1,
6,
7,
11
};
size = sizeof(sequence2)/sizeof(sequence2[0]);;
obj.check_sequence(sequence2, size);
return 0;
}
Output
1 3 5 6 7 9
Sequence Are Exist : 1 6 7
Sequence Are Not Exist : 1 6 7 11//Java program
//Check if given sorted sub-sequence exists in binary search tree
//BST node
class Node {
public int data;
public Node left;
public Node right;
public Node(int value) {
data = value;
left = null;
right = null;
}
}
public class BinarySearchTree {
public Node root;
public int location;
public BinarySearchTree() {
root = null;
location = 0;
}
//insert a node in BST
public void add(int value) {
//Create a dynamic node of binary search tree
Node new_node = new Node(value);
if (new_node != null) {
if (root == null) {
//When adds a first node in binary tree
root = new_node;
} else {
Node find = root;
//add new node to proper position
while (find != null) {
if (find.data >= value) {
if (find.left == null) {
find.left = new_node;
break;
} else {
//visit left sub-tree
find = find.left;
}
} else {
if (find.right == null) {
find.right = new_node;
break;
} else {
//visit right sub-tree
find = find.right;
}
}
}
}
} else {
System.out.print("\nMemory Overflow\n");
}
}
public void inorder(Node head) {
if (head != null) {
inorder(head.left);
System.out.print(head.data + " ");
inorder(head.right);
}
}
public void compare_element(Node head,int []sequence, int size)
{
if(head!=null)
{
compare_element(head.left,sequence,size);
if(this.location < size && head.data==sequence[this.location])
{
this.location++;
}
compare_element(head.right,sequence,size);
}
}
public void display(int []sequence,int size)
{
int i = 0;
while(i<size)
{
System.out.print(" "+sequence[i]);
i++;
}
}
public void check_sequence(int []sequence,int size)
{
if(size<=0)
{
//invalid sequence size
return;
}
else if(this.root != null )
{
this.location = 0;
compare_element(this.root,sequence,size);
if(this.location < size)
{
System.out.print("\nSequence Are Not Exist : " );
}
else
{
System.out.print("\nSequence Are Exist : ");
}
display(sequence,size);
}
else
{
System.out.print("\n Empty Tree\n");
}
}
public static void main(String[] args) {
BinarySearchTree obj = new BinarySearchTree();
//Add nodes in binary search tree
/*
6
/ \
/ \
3 9
/ \ /
1 5 7
inorder = 1,3,5,6,7,9
*/
obj.add(6);
obj.add(3);
obj.add(9);
obj.add(1);
obj.add(5);
obj.add(7);
obj.inorder(obj.root);
int []sequence1={1,6,7};
int size = sequence1.length;
obj.check_sequence(sequence1,size);
int []sequence2={1,6,7,11};
size = sequence2.length;
obj.check_sequence(sequence2,size);
}
}
Output
1 3 5 6 7 9
Sequence Are Exist : 1 6 7
Sequence Are Not Exist : 1 6 7 11//C# program
//Check if given sorted sub-sequence exists in binary search tree
using System;
//BST node
public class Node {
public int data;
public Node left;
public Node right;
public Node(int value) {
data = value;
left = null;
right = null;
}
}
public class BinarySearchTree {
public Node root;
public int location;
public BinarySearchTree() {
root = null;
location = 0;
}
//insert a node in BST
public void add(int value) {
//Create a dynamic node of binary search tree
Node new_node = new Node(value);
if (new_node != null) {
if (root == null) {
//When adds a first node in binary tree
root = new_node;
} else {
Node find = root;
//add new node to proper position
while (find != null) {
if (find.data >= value) {
if (find.left == null) {
find.left = new_node;
break;
} else {
//visit left sub-tree
find = find.left;
}
} else {
if (find.right == null) {
find.right = new_node;
break;
} else {
//visit right sub-tree
find = find.right;
}
}
}
}
} else {
Console.Write("\nMemory Overflow\n");
}
}
public void inorder(Node head) {
if (head != null) {
inorder(head.left);
Console.Write(head.data + " ");
inorder(head.right);
}
}
public void compare_element(Node head,int []sequence, int size)
{
if(head!=null)
{
compare_element(head.left,sequence,size);
if(this.location < size && head.data==sequence[this.location])
{
this.location++;
}
compare_element(head.right,sequence,size);
}
}
public void display(int []sequence,int size)
{
int i = 0;
while(i<size)
{
Console.Write(" "+sequence[i]);
i++;
}
}
public void check_sequence(int []sequence,int size)
{
if(size<=0)
{
//invalid sequence size
return;
}
else if(this.root != null )
{
this.location = 0;
compare_element(this.root,sequence,size);
if(this.location < size)
{
Console.Write("\nSequence Are Not Exist : " );
}
else
{
Console.Write("\nSequence Are Exist : ");
}
display(sequence,size);
}
else
{
Console.Write("\n Empty Tree\n");
}
}
public static void Main(String[] args) {
BinarySearchTree obj = new BinarySearchTree();
//Add nodes in binary search tree
/*
6
/ \
/ \
3 9
/ \ /
1 5 7
inorder = 1,3,5,6,7,9
*/
obj.add(6);
obj.add(3);
obj.add(9);
obj.add(1);
obj.add(5);
obj.add(7);
obj.inorder(obj.root);
int []sequence1={1,6,7};
int size = sequence1.Length;
obj.check_sequence(sequence1,size);
int []sequence2={1,6,7,11};
size = sequence2.Length;
obj.check_sequence(sequence2,size);
}
}
Output
1 3 5 6 7 9
Sequence Are Exist : 1 6 7
Sequence Are Not Exist : 1 6 7 11# Python 3 Program
# Check if given sorted sub-sequence exists in binary search tree
class Node :
def __init__(self, value) :
self.data = value
self.left = None
self.right = None
class BinarySearchTree :
def __init__(self) :
self.root = None
self.location = 0
def add(self, value) :
new_node = Node(value)
if (new_node != None) :
if (self.root == None) :
self.root = new_node
else :
find = self.root
while (find != None) :
if (find.data >= value) :
if (find.left == None) :
find.left = new_node
break
else :
find = find.left
else :
if (find.right == None) :
find.right = new_node
break
else :
find = find.right
else :
print("\nMemory Overflow\n")
def inorder(self, head) :
if (head != None) :
self.inorder(head.left)
print(head.data ,end=" ")
self.inorder(head.right)
def compare_element(self, head, sequence, size) :
if (head != None) :
self.compare_element(head.left, sequence, size)
if (self.location < size and head.data == sequence[self.location]) :
self.location += 1
self.compare_element(head.right, sequence, size)
def display(self, sequence, size) :
i = 0
while (i < size) :
print( sequence[i],end=" ")
i += 1
def check_sequence(self, sequence, size) :
if (size <= 0) :
return
elif (self.root != None) :
self.location = 0
self.compare_element(self.root, sequence, size)
if (self.location < size) :
print("\nSequence Are Not Exist : ",end=" ")
else :
print("\nSequence Are Exist : ",end=" ")
self.display(sequence, size)
else :
print("\n Empty Tree\n")
def main() :
obj = BinarySearchTree()
#
# 6
# / \
# / \
# 3 9
# / \ /
# 1 5 7
# inorder = 1,3,5,6,7,9
#
obj.add(6)
obj.add(3)
obj.add(9)
obj.add(1)
obj.add(5)
obj.add(7)
obj.inorder(obj.root)
sequence1 = [1, 6, 7]
size = len(sequence1)
obj.check_sequence(sequence1, size)
sequence2 = [1, 6, 7, 11]
size = len(sequence2)
obj.check_sequence(sequence2, size)
if __name__ == "__main__":
main()
Output
1 3 5 6 7 9
Sequence Are Exist : 1 6 7
Sequence Are Not Exist : 1 6 7 11# Ruby Program
# Check if given sorted sub-sequence exists in binary search tree
class Node
attr_reader :data, :left, :right
attr_accessor :data, :left, :right
def initialize(value)
@data = value
@left = nil
@right = nil
end
end
class BinarySearchTree
attr_reader :root, :location
attr_accessor :root, :location
def initialize()
@root = nil
@location = 0
end
def add(value)
new_node = Node.new(value)
if (new_node != nil)
if (@root == nil)
@root = new_node
else
find = @root
while (find != nil)
if (find.data >= value)
if (find.left == nil)
find.left = new_node
break
else
find = find.left
end
else
if (find.right == nil)
find.right = new_node
break
else
find = find.right
end
end
end
end
else
print("\nMemory Overflow\n")
end
end
def inorder(head)
if (head != nil)
self.inorder(head.left)
print(head.data ," ")
self.inorder(head.right)
end
end
def compare_element(head, sequence, size)
if (head != nil)
self.compare_element(head.left, sequence, size)
if (self.location < size and head.data == sequence[self.location])
self.location += 1
end
self.compare_element(head.right, sequence, size)
end
end
def display(sequence, size)
i = 0
while (i < size)
print(" ", sequence[i])
i += 1
end
end
def check_sequence(sequence, size)
if (size <= 0)
return
elsif (self.root != nil)
self.location = 0
self.compare_element(self.root, sequence, size)
if (self.location < size)
print("\nSequence Are Not Exist :")
else
print("\nSequence Are Exist :")
end
self.display(sequence, size)
else
print("\n Empty Tree\n")
end
end
end
def main()
obj = BinarySearchTree.new()
#
# 6
# / \
# / \
# 3 9
# / \ /
# 1 5 7
# inorder = 1,3,5,6,7,9
#
obj.add(6)
obj.add(3)
obj.add(9)
obj.add(1)
obj.add(5)
obj.add(7)
obj.inorder(obj.root)
sequence1 = [1, 6, 7]
size = sequence1.length
obj.check_sequence(sequence1, size)
sequence2 = [1, 6, 7, 11]
size = sequence2.length
obj.check_sequence(sequence2, size)
end
main()
Output
1 3 5 6 7 9
Sequence Are Exist : 1 6 7
Sequence Are Not Exist : 1 6 7 11<?php
/*
Php Program
Check if given sorted sub-sequence exists in binary search tree
*/
class Node {
public $data;
public $left;
public $right;
function __construct($value) {
$this->data = $value;
$this->left = null;
$this->right = null;
}
}
class BinarySearchTree {
public $root;
public $location;
function __construct() {
$this->root = null;
$this->location = 0;
}
public function add($value) {
$new_node = new Node($value);
if ($new_node != null) {
if ($this->root == null) {
$this->root = $new_node;
} else {
$find = $this->root;
while ($find != null) {
if ($find->data >= $value) {
if ($find->left == null) {
$find->left = $new_node;
break;;
} else {
$find = $find->left;
}
} else {
if ($find->right == null) {
$find->right = $new_node;
break;;
} else {
$find = $find->right;
}
}
}
}
} else {
echo("\nMemory Overflow\n");
}
}
public function inorder($head) {
if ($head != null) {
$this->inorder($head->left);
echo($head->data ." ");
$this->inorder($head->right);
}
}
public function compare_element($head, $sequence, $size) {
if ($head != null) {
$this->compare_element($head->left, $sequence, $size);
if ($this->location < $size && $head->data == $sequence[$this->location]) {
$this->location++;
}
$this->compare_element($head->right, $sequence, $size);
}
}
public function display($sequence, $size) {
$i = 0;
while ($i < $size) {
echo(" ". $sequence[$i]);
$i++;
}
}
public function check_sequence($sequence, $size) {
if ($size <= 0) {
return;
} else
if ($this->root != null) {
$this->location = 0;
$this->compare_element($this->root, $sequence, $size);
if ($this->location < $size) {
echo("\nSequence Are Not Exist : ");
} else {
echo("\nSequence Are Exist : ");
}
$this->display($sequence, $size);
} else {
echo("\n Empty Tree\n");
}
}
}
function main() {
$obj = new BinarySearchTree();
/*
6
/ \
/ \
3 9
/ \ /
1 5 7
inorder = 1,3,5,6,7,9
*/
$obj->add(6);
$obj->add(3);
$obj->add(9);
$obj->add(1);
$obj->add(5);
$obj->add(7);
$obj->inorder($obj->root);
$sequence1 = array(1, 6, 7);
$size = count($sequence1);
$obj->check_sequence($sequence1, $size);
$sequence2 = array(1, 6, 7, 11);
$size = count($sequence2);
$obj->check_sequence($sequence2, $size);
}
main();
Output
1 3 5 6 7 9
Sequence Are Exist : 1 6 7
Sequence Are Not Exist : 1 6 7 11/*
Node Js Program
Check if given sorted sub-sequence exists in binary search tree
*/
class Node {
constructor(value) {
this.data = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
this.location = 0;
}
add(value) {
var new_node = new Node(value);
if (new_node != null) {
if (this.root == null) {
this.root = new_node;
} else {
var find = this.root;
while (find != null) {
if (find.data >= value) {
if (find.left == null) {
find.left = new_node;
break;;
} else {
find = find.left;
}
} else {
if (find.right == null) {
find.right = new_node;
break;;
} else {
find = find.right;
}
}
}
}
} else {
process.stdout.write("\nMemory Overflow\n");
}
}
inorder(head) {
if (head != null) {
this.inorder(head.left);
process.stdout.write(head.data + " ");
this.inorder(head.right);
}
}
compare_element(head, sequence, size) {
if (head != null) {
this.compare_element(head.left, sequence, size);
if (this.location < size && head.data == sequence[this.location]) {
this.location++;
}
this.compare_element(head.right, sequence, size);
}
}
display(sequence, size) {
var i = 0;
while (i < size) {
process.stdout.write(" " + sequence[i]);
i++;
}
}
check_sequence(sequence, size) {
if (size <= 0) {
return;
} else
if (this.root != null) {
this.location = 0;
this.compare_element(this.root, sequence, size);
if (this.location < size) {
process.stdout.write("\nSequence Are Not Exist : ");
} else {
process.stdout.write("\nSequence Are Exist : ");
}
this.display(sequence, size);
} else {
process.stdout.write("\n Empty Tree\n");
}
}
}
function main() {
var obj = new BinarySearchTree();
/*
6
/ \
/ \
3 9
/ \ /
1 5 7
inorder = 1,3,5,6,7,9
*/
obj.add(6);
obj.add(3);
obj.add(9);
obj.add(1);
obj.add(5);
obj.add(7);
obj.inorder(obj.root);
var sequence1 = [1, 6, 7];
var size = sequence1.length;
obj.check_sequence(sequence1, size);
var sequence2 = [1, 6, 7, 11];
size = sequence2.length;
obj.check_sequence(sequence2, size);
}
main();
Output
1 3 5 6 7 9
Sequence Are Exist : 1 6 7
Sequence Are Not Exist : 1 6 7 11/*
Swift 4 Program
Check if given sorted sub-sequence exists in binary search tree
*/
class Node {
var data: Int;
var left: Node? ;
var right: Node? ;
init(_ value: Int) {
self.data = value;
self.left = nil;
self.right = nil;
}
}
class BinarySearchTree {
var root: Node? ;
var location: Int;
init() {
self.root = nil;
self.location = 0;
}
func add(_ value: Int) {
let new_node: Node? = Node(value);
if (new_node != nil) {
if (self.root == nil) {
self.root = new_node;
} else {
var find: Node? = self.root;
while (find != nil) {
if (find!.data >= value) {
if (find!.left == nil) {
find!.left = new_node;
break;
} else {
find = find!.left;
}
} else {
if (find!.right == nil) {
find!.right = new_node;
break;
} else {
find = find!.right;
}
}
}
}
} else {
print("\nMemory Overflow\n");
}
}
func inorder(_ head: Node? ) {
if (head != nil) {
self.inorder(head!.left);
print(head!.data ,terminator:" ");
self.inorder(head!.right);
}
}
func compare_element(_ head: Node? , _ sequence : [Int] , _ size : Int) {
if (head != nil) {
self.compare_element(head!.left, sequence, size);
if (self.location < size && head!.data == sequence[self.location]) {
self.location += 1;
}
self.compare_element(head!.right, sequence, size);
}
}
func display(_ sequence: [Int] , _ size : Int) {
var i: Int = 0;
while (i < size) {
print(sequence[i],terminator:" ");
i += 1;
}
}
func check_sequence(_ sequence: [Int] , _ size : Int) {
if (size <= 0) {
return;
} else
if (self.root != nil) {
self.location = 0;
self.compare_element(self.root, sequence, size);
if (self.location < size) {
print("\nSequence Are Not Exist : ",terminator:" ");
} else {
print("\nSequence Are Exist : ",terminator:" ");
}
self.display(sequence, size);
} else {
print("\n Empty Tree\n");
}
}
}
func main() {
let obj: BinarySearchTree = BinarySearchTree();
/*
6
/ \
/ \
3 9
/ \ /
1 5 7
inorder = 1,3,5,6,7,9
*/
obj.add(6);
obj.add(3);
obj.add(9);
obj.add(1);
obj.add(5);
obj.add(7);
obj.inorder(obj.root);
let sequence1: [Int] = [1, 6, 7];
var size: Int = sequence1.count;
obj.check_sequence(sequence1, size);
let sequence2: [Int] = [1, 6, 7, 11];
size = sequence2.count;
obj.check_sequence(sequence2, size);
}
main();
Output
1 3 5 6 7 9
Sequence Are Exist : 1 6 7
Sequence Are Not Exist : 1 6 7 11
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment