Posted on by Kalkicode
Code Binary Search Tree

# Check if two BST contain same set of elements

Here given code implementation process.

``````//C Program
//Check if two BST contain same set of elements
#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
}

}
int  count_element(struct Node*root)
{
if(root!=NULL)
{
return count_element(root->left)+count_element(root->right)+1;
}
return 0;

}
void get_element(struct Node*root,int *index,int *auxiliary)
{
if(root!=NULL)
{
get_element(root->left,index,auxiliary);

auxiliary[*index]=root->data;
(*index)++;
get_element(root->right,index,auxiliary);
}

}
void compare_element(struct Node*root,int *index,int *auxiliary)
{

if(root!=NULL)
{
compare_element(root->left,index,auxiliary);

if(root->data==auxiliary[*index])
{
(*index)++;
}
compare_element(root->right,index,auxiliary);
}

}
void same_set(struct Node*root1,struct Node*root2)
{
if(root1 != NULL && root2)
{
int size=count_element(root1);

if(size==count_element(root2))
{
int *auxiliary=(int*)malloc(sizeof(int)*size);
int index=0;
get_element(root1,&index,auxiliary);
index=0;
compare_element(root2,&index,auxiliary);
if(index<size)
{
//When node element value are not similar
printf("\n Not\n");
}
else
{
printf("\n Yes\n");
}

free(auxiliary);
auxiliary=NULL;

}
else
{
//When length of nodes are not same in Tree
printf("\n Not\n");
}
}
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*root1 = NULL,*root2=NULL;

//Add nodes in binary search tree
/*
6
/    \
/      \
3        9
/  \      /
1    5    7

inorder = 1,3,5,6,7,9
*/

/*
3
/   \
1     7
/  \
5    9
\
6
inorder = 1,3,5,6,7,9
*/

printf("First Tree inorder  \n");
inorder(root1);

printf("\nSecond Tree inorder \n");
inorder(root2);

same_set(root1,root2);
return 0;
}```
```

#### Output

``````First Tree inorder
1   3   5   6   7   9
Second Tree inorder
1   3   5   6   7   9
Yes
``````
``````/*
C++ Program
Check if two BST contain same set of elements
*/

#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 counter;
BinarySearchTree() {
this->root = NULL;
this->counter = 0;
}
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";
}
}
}
return 0;
}
void get_elements(Node *head, int auxiliary[]) {
this->counter++;
}
}
void compare_element(Node *head, int auxiliary[]) {
this->counter++;
}
}
}
void same_set(Node *root1, Node *root2) {
if (root1 == NULL && root2 != NULL && root2 == NULL && root1 != NULL) {
cout<< "\nNo\n";
} else {
int size = this->counter_nodes(root1);
if (size != this->counter_nodes(root2)) {
cout << "\nNo\n";
return;
}
int *auxiliary = new int[size];

this->counter = 0;
this->get_elements(root1, auxiliary);
this->counter = 0;
this->compare_element(root2, auxiliary);
if (this->counter != size) {
cout << "\nNo\n";
} else {
cout << "\nYes\n";
}
}
}
cout << head->data << "  ";
}
}
};

int main() {
BinarySearchTree obj1;
BinarySearchTree obj2;
/*
6
/    \
/      \
3        9
/  \      /
1    5    7

inorder = 1,3,5,6,7,9
*/

/*
3
/   \
1     7
/  \
5    9
\
6
inorder = 1,3,5,6,7,9
*/
cout << "First Tree inorder  \n";
obj1.inorder(obj1.root);
cout << "\nSecond Tree inorder  \n";
obj2.inorder(obj2.root);
obj1.same_set(obj1.root, obj2.root);

return 0;
}```
```

#### Output

``````First Tree inorder
1   3   5   6   7   9
Second Tree inorder
1   3   5   6   7   9
Yes
``````
``````//Java program
//Check if two BST contain same set of elements

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 counter;

BinarySearchTree() {
root = null;
counter = 0;
}
//insert a node in BST
//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");
}
}

}
return 0;
}
public void get_elements(Node head, int[] auxiliary) {

this.counter++;

}
}
public void compare_element(Node head, int[] auxiliary) {

this.counter++;
}
}

}
public void same_set(Node root1, Node root2) {
if (root1 == null && root2 != null && root2 == null && root1 != null) {
System.out.print("\nNo\n");
} else {

int size = counter_nodes(root1);

if (size != counter_nodes(root2)) {
//not same set of elements
System.out.print("\nNo\n");
return;
}

int[] auxiliary = new int[size];

this.counter = 0;

get_elements(root1, auxiliary);

this.counter = 0;

compare_element(root2, auxiliary);

if (this.counter != size) {
System.out.print("\nNo\n");
} else {
System.out.print("\nYes\n");
}
}

}

}
}
public static void main(String[] args) {

BinarySearchTree obj1 = new BinarySearchTree();
BinarySearchTree obj2 = new BinarySearchTree();
//Add nodes in binary search tree
/*
6
/    \
/      \
3        9
/  \      /
1    5    7

inorder = 1,3,5,6,7,9
*/

/*
3
/   \
1     7
/  \
5    9
\
6
inorder = 1,3,5,6,7,9
*/

System.out.print("First Tree inorder  \n");
obj1.inorder(obj1.root);

System.out.print("\nSecond Tree inorder   \n");
obj2.inorder(obj2.root);

obj1.same_set(obj1.root, obj2.root);
}
}```
```

#### Output

``````First Tree inorder
1   3   5   6   7   9
Second Tree inorder
1   3   5   6   7   9
Yes
``````
``````//C# program
//Check if two BST contain same set of elements
using System;
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 counter;

BinarySearchTree() {
root = null;
counter = 0;
}
//insert a node in BST
//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");
}
}

}
return 0;
}
public void get_elements(Node head, int[] auxiliary) {

this.counter++;

}
}
public void compare_element(Node head, int[] auxiliary) {

this.counter++;
}
}

}
public void same_set(Node root1, Node root2) {
if (root1 == null && root2 != null && root2 == null && root1 != null) {
Console.Write("\nNo\n");
} else {

int size = counter_nodes(root1);

if (size != counter_nodes(root2)) {
//not same set of elements
Console.Write("\nNo\n");
return;
}

int[] auxiliary = new int[size];

this.counter = 0;

get_elements(root1, auxiliary);

this.counter = 0;

compare_element(root2, auxiliary);

if (this.counter != size) {
Console.Write("\nNo\n");
} else {
Console.Write("\nYes\n");
}
}

}

}
}
public static void Main(String[] args) {

BinarySearchTree obj1 = new BinarySearchTree();
BinarySearchTree obj2 = new BinarySearchTree();
//Add nodes in binary search tree
/*
6
/    \
/      \
3        9
/  \      /
1    5    7

inorder = 1,3,5,6,7,9
*/

/*
3
/   \
1     7
/  \
5    9
\
6
inorder = 1,3,5,6,7,9
*/

Console.Write("First Tree inorder  \n");
obj1.inorder(obj1.root);

Console.Write("\nSecond Tree inorder   \n");
obj2.inorder(obj2.root);

obj1.same_set(obj1.root, obj2.root);
}
}```
```

#### Output

``````First Tree inorder
1   3   5   6   7   9
Second Tree inorder
1   3   5   6   7   9
Yes
``````
``````# Python 3 Program
# Check if two BST contain same set of elements

class Node :
def __init__(self, value) :
self.data = value
self.left = None
self.right = None

class BinarySearchTree :

def __init__(self) :
self.root = None
self.counter = 0

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")

return 0

self.counter += 1

self.counter += 1

def same_set(self, root1, root2) :
if (root1 == None and root2 != None and root2 == None and root1 != None) :
print("\nNo\n")
else :
size = self.counter_nodes(root1)
if (size != self.counter_nodes(root2)) :
print("\nNo\n")
return

auxiliary = [0]*size

self.counter = 0
self.get_elements(root1, auxiliary)
self.counter = 0
self.compare_element(root2, auxiliary)
if (self.counter != size) :
print("\nNo\n")
else :
print("\nYes\n")

def main() :
obj1 = BinarySearchTree()
obj2 = BinarySearchTree()

#
#          6
#        /    \
#       /      \
#      3        9
#     /  \      /
#    1    5    7
#    inorder = 1,3,5,6,7,9
#

#
#        3
#      /   \
#     1     7
#          /  \
#         5    9
#          \
#           6
#    inorder = 1,3,5,6,7,9
#
print("First Tree inorder  ")
obj1.inorder(obj1.root)
print("\nSecond Tree inorder   ")
obj2.inorder(obj2.root)
obj1.same_set(obj1.root, obj2.root)

if __name__ == "__main__":
main()```
```

#### Output

``````First Tree inorder
1   3   5   6   7   9
Second Tree inorder
1   3   5   6   7   9
Yes
``````
``````# Ruby Program
# Check if two BST contain same set of elements

class Node
attr_accessor :data, :left, :right
def initialize(value)
@data = value
@left = nil
@right = nil
end
end

class BinarySearchTree
attr_accessor :root, :counter
def initialize()
@root = nil
@counter = 0
end
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
end
return 0
end
self.counter += 1
end
end
self.counter += 1
end
end
end
def same_set(root1, root2)
if (root1 == nil and root2 != nil and root2 == nil and root1 != nil)
print("\nNo\n")
else
size = self.counter_nodes(root1)
if (size != self.counter_nodes(root2))
print("\nNo\n")
return
end
auxiliary = Array.new(size,0)

self.counter = 0
self.get_elements(root1, auxiliary)
self.counter = 0
self.compare_element(root2, auxiliary)
if (self.counter != size)
print("\nNo\n")
else
print("\nYes\n")
end
end
end
end
end
end

def main()
obj1 = BinarySearchTree.new()
obj2 = BinarySearchTree.new()

#
#          6
#        /    \
#       /      \
#      3        9
#     /  \      /
#    1    5    7
#    inorder = 1,3,5,6,7,9
#

#
#        3
#      /   \
#     1     7
#          /  \
#         5    9
#          \
#           6
#    inorder = 1,3,5,6,7,9
#
print("First Tree inorder  \n")
obj1.inorder(obj1.root)
print("\nSecond Tree inorder   \n")
obj2.inorder(obj2.root)
obj1.same_set(obj1.root, obj2.root)
end
main()```
```

#### Output

``````First Tree inorder
1   3   5   6   7   9
Second Tree inorder
1   3   5   6   7   9
Yes
``````
``````<?php
/*
Php Program
Check if two BST contain same set of elements
*/

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 \$counter;

function __construct() {
\$this->root = null;
\$this->counter = 0;
}
\$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");
}
}
}
return 0;
}
\$this->counter++;
}
}
\$this->counter++;
}
}
}
public  function same_set(\$root1, \$root2) {
if (\$root1 == null && \$root2 != null && \$root2 == null && \$root1 != null) {
echo("\nNo\n");
} else {
\$size = \$this->counter_nodes(\$root1);
if (\$size != \$this->counter_nodes(\$root2)) {
echo("\nNo\n");
return;
}
\$auxiliary = array_fill(0, \$size, 0);

\$this->counter = 0;
\$this->get_elements(\$root1, \$auxiliary);
\$this->counter = 0;
\$this->compare_element(\$root2, \$auxiliary);
if (\$this->counter != \$size) {
echo("\nNo\n");
} else {
echo("\nYes\n");
}
}
}
}
}

}
function main() {
\$obj1 = new BinarySearchTree();
\$obj2 = new BinarySearchTree();
/*
6
/    \
/      \
3        9
/  \      /
1    5    7

inorder = 1,3,5,6,7,9
*/
/*
3
/   \
1     7
/  \
5    9
\
6
inorder = 1,3,5,6,7,9
*/
echo("First Tree inorder  \n");
\$obj1->inorder(\$obj1->root);
echo("\nSecond Tree inorder   \n");
\$obj2->inorder(\$obj2->root);
\$obj1->same_set(\$obj1->root, \$obj2->root);
}
main();```
```

#### Output

``````First Tree inorder
1   3   5   6   7   9
Second Tree inorder
1   3   5   6   7   9
Yes
``````
``````/*
Node Js Program
Check if two BST contain same set of elements
*/

class Node {
constructor(value) {
this.data = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {

constructor() {
this.root = null;
this.counter = 0;
}
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");
}
}
}
return 0;
}
this.counter++;
}
}
this.counter++;
}
}
}
same_set(root1, root2) {
if (root1 == null && root2 != null && root2 == null && root1 != null) {
process.stdout.write("\nNo\n");
} else {
var size = this.counter_nodes(root1);
if (size != this.counter_nodes(root2)) {
process.stdout.write("\nNo\n");
return;
}
var auxiliary = Array(size).fill(0);
this.counter = 0;
this.get_elements(root1, auxiliary);
this.counter = 0;
this.compare_element(root2, auxiliary);
if (this.counter != size) {
process.stdout.write("\nNo\n");
} else {
process.stdout.write("\nYes\n");
}
}
}
}
}
}

function main() {
var obj1 = new BinarySearchTree();
var obj2 = new BinarySearchTree();
/*
6
/    \
/      \
3        9
/  \      /
1    5    7

inorder = 1,3,5,6,7,9
*/
/*
3
/   \
1     7
/  \
5    9
\
6
inorder = 1,3,5,6,7,9
*/
process.stdout.write("First Tree inorder  \n");
obj1.inorder(obj1.root);
process.stdout.write("\nSecond Tree inorder   \n");
obj2.inorder(obj2.root);
obj1.same_set(obj1.root, obj2.root);
}

main();```
```

#### Output

``````First Tree inorder
1   3   5   6   7   9
Second Tree inorder
1   3   5   6   7   9
Yes
``````
``````/*
Swift 4 Program
Check if two BST contain same set of elements
*/

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 counter: Int;
init() {
self.root = nil;
self.counter = 0;
}
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 counter_nodes(_ head: Node? ) -> Int{
}
return 0;
}
func get_elements(_ head: Node? , _ auxiliary : inout [Int] ) {
self.counter += 1;
}
}
func compare_element(_ head: Node? , _ auxiliary : [Int] ) {
self.counter += 1;
}
}
}
func same_set(_ root1: Node? , _ root2 : Node? ) {
if (root1 == nil && root2 != nil && root2 == nil && root1 != nil) {
print("\nNo\n");
} else {
let size: Int = self.counter_nodes(root1);
if (size != self.counter_nodes(root2)) {
print("\nNo\n");
return;
}
var auxiliary: [Int] = Array(repeating:0,count:size);
self.counter = 0;
self.get_elements(root1, &auxiliary);
self.counter = 0;
self.compare_element(root2, auxiliary);
if (self.counter != size) {
print("\nNo\n");
} else {
print("\nYes\n");
}
}
}
func inorder(_ head: Node? ) {
}
}
}
func main() {
let obj1: BinarySearchTree  = BinarySearchTree();
let obj2: BinarySearchTree  = BinarySearchTree();
/*
6
/    \
/      \
3        9
/  \      /
1    5    7

inorder = 1,3,5,6,7,9
*/

/*
3
/   \
1     7
/  \
5    9
\
6
inorder = 1,3,5,6,7,9
*/
print("First Tree inorder  ");
obj1.inorder(obj1.root);
print("\nSecond Tree inorder ");
obj2.inorder(obj2.root);
obj1.same_set(obj1.root, obj2.root);
}
main();```
```

#### Output

``````First Tree inorder
1   3   5   6   7   9
Second Tree inorder
1   3   5   6   7   9
Yes
``````

## Comment

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.

Categories
Relative Post