Determine whether given two BST are identical or not
Here given code implementation process.
//C Program
//Determine whether given two BST are identical or not
#include <stdio.h>
#include <stdlib.h>
//structure of Binary Search Tree BST
struct BST
{
int data;
struct BST *left, *right;
};
//Adding a new BST in binary search tree
void add(struct BST **root, int data)
{
//Create a dynamic BST of binary search tree
struct BST *new_BST = (struct BST *) malloc(sizeof(struct BST));
if (new_BST != NULL)
{
//Set data and pointer values
new_BST->data = data;
new_BST->left = NULL; //Initially BST left-pointer is NULL
new_BST->right = NULL; //Initially BST right-pointer is NULL
if ( *root == NULL)
{
//When adds a first BST in binary tree
*root = new_BST;
}
else
{
struct BST *find = *root;
//iterate binary tree and add new BST to proper position
while (find != NULL)
{
if (find->data > data)
{
if (find->left == NULL)
{
find->left = new_BST;
break;
}
else
{ //visit left sub-tree
find = find->left;
}
}
else
{
if (find->right == NULL)
{
find->right = new_BST;
break;
}
else
{
//visit right sub-tree
find = find->right;
}
}
}
}
}
else
{
printf("Memory Overflow\n");
exit(0); //Terminate program execution
}
}
//Display tree element inorder form
void inorder(struct BST *root)
{
if (root != NULL)
{
inorder(root->left);
//Print node value
printf(" %d", root->data);
inorder(root->right);
}
}
int is_identical(struct BST *tree1, struct BST *tree2)
{
if (tree1 == NULL && tree2 == NULL)
{
//When both tree nodes are empty
return 1;
}
else if (tree1 != NULL && tree2 != NULL && tree1->data == tree2->data)
{
//Compare the value of left and right child node data
return is_identical(tree1->left, tree2->left) && is_identical(tree1->right, tree2->right);
}
else
{
//when one tree is empty and other is not empty
//Or if tree node data are not same
return 0;
}
}
//This function are display the result of given tree is identical tree or not
void check_identical(struct BST *tree1, struct BST *tree2)
{
//Display tree data
printf("\n Given First Tree Inorder Data \n");
inorder(tree1);
printf("\n Given Second Tree Inorder Data \n");
inorder(tree2);
if (is_identical(tree1, tree2) == 1)
{
printf("\n Is Identical Tree\n");
}
else
{
printf("\n Is not Identical Tree\n");
}
}
int main()
{
struct BST *root1 = NULL, *root2 = NULL, *root3 = NULL;
/*
7
/ \
4 11
/ \ \
2 5 15
\ /
3 13
*/
//Add first tree node
add( & root1, 7);
add( & root1, 4);
add( & root1, 11);
add( & root1, 2);
add( & root1, 5);
add( & root1, 15);
add( & root1, 3);
add( & root1, 13);
/*
7
/ \
4 11
/ \ \
2 5 15
\ / \
3 13 17
*/
//Add second tree node
add( & root2, 7);
add( & root2, 4);
add( & root2, 11);
add( & root2, 2);
add( & root2, 5);
add( & root2, 15);
add( & root2, 3);
add( & root2, 13);
add( & root2, 17);
/*
7
/ \
4 11
/ \ \
2 5 15
\ /
3 13
*/
//Add third tree node
add( & root3, 7);
add( & root3, 4);
add( & root3, 11);
add( & root3, 2);
add( & root3, 5);
add( & root3, 15);
add( & root3, 3);
add( & root3, 13);
//Test Case
check_identical(root1, root2);
check_identical(root1, root3);
check_identical(root2, root3);
return 0;
}Output
Given First Tree Inorder Data
2 3 4 5 7 11 13 15
Given Second Tree Inorder Data
2 3 4 5 7 11 13 15 17
Is not Identical Tree
Given First Tree Inorder Data
2 3 4 5 7 11 13 15
Given Second Tree Inorder Data
2 3 4 5 7 11 13 15
Is Identical Tree
Given First Tree Inorder Data
2 3 4 5 7 11 13 15 17
Given Second Tree Inorder Data
2 3 4 5 7 11 13 15
Is not Identical Tree/*
Java Program
Determine whether given two BST are identical or not
*/
//Tree node
class BST
{
public int data;
public BST left;
public BST right;
public BST(int data)
{
//Set data value of binary tree node
this.data = data;
this.left = null;
this.right = null;
}
}
class BinarySearchTree
{
public BST root;
public BinarySearchTree()
{
root = null;
}
//insert a node in BST
public void add(int value)
{
//Create a dynamic node of binary search tree
BST new_node = new BST(value);
if (new_node != null)
{
if (root == null)
{
//When adds a first node in binary tree
root = new_node;
}
else
{
BST 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");
}
}
//Display tree element inorder form
public void inorder(BST root)
{
if (root != null)
{
inorder(root.left);
System.out.print(" " + root.data + "");
inorder(root.right);
}
}
public boolean is_identical(BST tree1, BST tree2)
{
if (tree1 == null && tree2 == null)
{
return true;
}
else if (tree1 != null && tree2 != null && tree1.data == tree2.data)
{
return is_identical(tree1.left, tree2.left) && is_identical(tree1.right, tree2. right);
}
else
{
return false;
}
}
//This function are display the result of given tree is identical tree or not
public void check_identical(BinarySearchTree tree1, BinarySearchTree tree2)
{
System.out.print("\n Given First Tree Inorder Data \n");
inorder(tree1.root);
System.out.print("\n Given Second Tree Inorder Data \n");
inorder(tree2.root);
if (is_identical(tree1.root, tree2.root) == true)
{
System.out.print("\n Is Identical Tree\n");
}
else
{
System.out.print("\n Is not Identical Tree\n");
}
}
public static void main(String[] args)
{
BinarySearchTree tree1 = new BinarySearchTree();
BinarySearchTree tree2 = new BinarySearchTree();
BinarySearchTree tree3 = new BinarySearchTree();
BinarySearchTree obj = new BinarySearchTree();
/*
7
/ \
4 11
/ \ \
2 5 15
\ /
3 13
*/
//Add first tree node
tree1.add( 7);
tree1.add( 4);
tree1.add( 11);
tree1.add( 2);
tree1.add( 5);
tree1.add( 15);
tree1.add( 3);
tree1.add( 13);
/*
7
/ \
4 11
/ \ \
2 5 15
\ / \
3 13 17
*/
//Add second tree node
tree2.add( 7);
tree2.add( 4);
tree2.add( 11);
tree2.add( 2);
tree2.add( 5);
tree2.add( 15);
tree2.add( 3);
tree2.add( 13);
tree2.add( 17);
/*
7
/ \
4 11
/ \ \
2 5 15
\ /
3 13
*/
//Add third tree node
tree3.add( 7);
tree3.add( 4);
tree3.add( 11);
tree3.add( 2);
tree3.add( 5);
tree3.add( 15);
tree3.add( 3);
tree3.add( 13);
//Test Case
obj.check_identical(tree1, tree2);
obj.check_identical(tree1, tree3);
obj.check_identical(tree2, tree3);
}
}Output
Given First Tree Inorder Data
2 3 4 5 7 11 13 15
Given Second Tree Inorder Data
2 3 4 5 7 11 13 15 17
Is not Identical Tree
Given First Tree Inorder Data
2 3 4 5 7 11 13 15
Given Second Tree Inorder Data
2 3 4 5 7 11 13 15
Is Identical Tree
Given First Tree Inorder Data
2 3 4 5 7 11 13 15 17
Given Second Tree Inorder Data
2 3 4 5 7 11 13 15
Is not Identical Tree/*
C++ Program
Determine whether given two BST are identical or not
*/
//Tree node
#include<iostream>
using namespace std;
class BST
{
public: int data;
BST *left;
BST *right;
BST(int data)
{
//Set data value of binary tree node
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
class BinarySearchTree
{
public: BST *root;
BinarySearchTree()
{
this->root = NULL;
}
//insert a node in BST
void add(int value)
{
//Create a dynamic node of binary search tree
BST *new_node = new BST(value);
if (new_node != NULL)
{
if (this->root == NULL)
{
//When adds a first node in binary tree
this->root = new_node;
}
else
{
BST *find = this->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
{
cout << "\nMemory Overflow\n";
}
}
//Display tree element inorder form
void inorder(BST *root)
{
if (root != NULL)
{
inorder(root->left);
cout << " " << root->data << "";
inorder(root->right);
}
}
bool is_identical(BST *tree1, BST *tree2)
{
if (tree1 == NULL && tree2 == NULL)
{
return true;
}
else if (tree1 != NULL && tree2 != NULL && tree1->data == tree2->data)
{
return is_identical(tree1->left, tree2->left) && is_identical(tree1->right, tree2->right);
}
else
{
return false;
}
}
//This function are display the result of given tree is identical tree or not
void check_identical(BinarySearchTree tree1, BinarySearchTree tree2)
{
cout << "\n Given First Tree Inorder Data \n";
inorder(tree1.root);
cout << "\n Given Second Tree Inorder Data \n";
inorder(tree2.root);
if (is_identical(tree1.root, tree2.root) == true)
{
cout << "\n Is Identical Tree\n";
}
else
{
cout << "\n Is not Identical Tree\n";
}
}
};
int main()
{
BinarySearchTree tree1 = BinarySearchTree();
BinarySearchTree tree2 = BinarySearchTree();
BinarySearchTree tree3 = BinarySearchTree();
BinarySearchTree obj = BinarySearchTree();
/*
7
/ \
4 11
/ \ \
2 5 15
\ /
3 13
*/
//Add first tree node
tree1.add(7);
tree1.add(4);
tree1.add(11);
tree1.add(2);
tree1.add(5);
tree1.add(15);
tree1.add(3);
tree1.add(13);
/*
7
/ \
4 11
/ \ \
2 5 15
\ / \
3 13 17
*/
//Add second tree node
tree2.add(7);
tree2.add(4);
tree2.add(11);
tree2.add(2);
tree2.add(5);
tree2.add(15);
tree2.add(3);
tree2.add(13);
tree2.add(17);
/*
7
/ \
4 11
/ \ \
2 5 15
\ /
3 13
*/
//Add third tree node
tree3.add(7);
tree3.add(4);
tree3.add(11);
tree3.add(2);
tree3.add(5);
tree3.add(15);
tree3.add(3);
tree3.add(13);
//Test Case
obj.check_identical(tree1, tree2);
obj.check_identical(tree1, tree3);
obj.check_identical(tree2, tree3);
return 0;
}Output
Given First Tree Inorder Data
2 3 4 5 7 11 13 15
Given Second Tree Inorder Data
2 3 4 5 7 11 13 15 17
Is not Identical Tree
Given First Tree Inorder Data
2 3 4 5 7 11 13 15
Given Second Tree Inorder Data
2 3 4 5 7 11 13 15
Is Identical Tree
Given First Tree Inorder Data
2 3 4 5 7 11 13 15 17
Given Second Tree Inorder Data
2 3 4 5 7 11 13 15
Is not Identical Tree/*
C# Program
Determine whether given two BST are identical or not
*/
using System;
//Tree node
class BST
{
public int data;
public BST left;
public BST right;
public BST(int data)
{
//Set data value of binary tree node
this.data = data;
this.left = null;
this.right = null;
}
}
class BinarySearchTree
{
public BST root;
public BinarySearchTree()
{
root = null;
}
//insert a node in BST
public void add(int value)
{
//Create a dynamic node of binary search tree
BST new_node = new BST(value);
if (new_node != null)
{
if (root == null)
{
//When adds a first node in binary tree
root = new_node;
}
else
{
BST 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");
}
}
//Display tree element inorder form
public void inorder(BST root)
{
if (root != null)
{
inorder(root.left);
Console.Write(" " + root.data + "");
inorder(root.right);
}
}
public Boolean is_identical(BST tree1, BST tree2)
{
if (tree1 == null && tree2 == null)
{
return true;
}
else if (tree1 != null && tree2 != null && tree1.data == tree2.data)
{
return is_identical(tree1.left, tree2.left) && is_identical(tree1.right, tree2.right);
}
else
{
return false;
}
}
//This function are display the result of given tree is identical tree or not
public void check_identical(BinarySearchTree tree1, BinarySearchTree tree2)
{
Console.Write("\n Given First Tree Inorder Data \n");
inorder(tree1.root);
Console.Write("\n Given Second Tree Inorder Data \n");
inorder(tree2.root);
if (is_identical(tree1.root, tree2.root) == true)
{
Console.Write("\n Is Identical Tree\n");
}
else
{
Console.Write("\n Is not Identical Tree\n");
}
}
public static void Main(String[] args)
{
BinarySearchTree tree1 = new BinarySearchTree();
BinarySearchTree tree2 = new BinarySearchTree();
BinarySearchTree tree3 = new BinarySearchTree();
BinarySearchTree obj = new BinarySearchTree();
//Add first tree node
tree1.add(7);
tree1.add(4);
tree1.add(11);
tree1.add(2);
tree1.add(5);
tree1.add(15);
tree1.add(3);
tree1.add(13);
//Add second tree node
tree2.add(7);
tree2.add(4);
tree2.add(11);
tree2.add(2);
tree2.add(5);
tree2.add(15);
tree2.add(3);
tree2.add(13);
tree2.add(17);
//Add third tree node
tree3.add(7);
tree3.add(4);
tree3.add(11);
tree3.add(2);
tree3.add(5);
tree3.add(15);
tree3.add(3);
tree3.add(13);
//Test Case
obj.check_identical(tree1, tree2);
obj.check_identical(tree1, tree3);
obj.check_identical(tree2, tree3);
}
}Output
Given First Tree Inorder Data
2 3 4 5 7 11 13 15
Given Second Tree Inorder Data
2 3 4 5 7 11 13 15 17
Is not Identical Tree
Given First Tree Inorder Data
2 3 4 5 7 11 13 15
Given Second Tree Inorder Data
2 3 4 5 7 11 13 15
Is Identical Tree
Given First Tree Inorder Data
2 3 4 5 7 11 13 15 17
Given Second Tree Inorder Data
2 3 4 5 7 11 13 15
Is not Identical Tree<?php
/*
Php Program
Determine whether given two BST are identical or not
*/
//Tree node
class BST
{
public $data;
public $left;
public $right;
function __construct($data)
{
//Set data value of binary tree node
$this->data = $data;
$this->left = null;
$this->right = null;
}
}
class BinarySearchTree
{
public $root;
function __construct()
{
$this->root = null;
}
//insert a node in BST
function add($value)
{
//Create a dynamic node of binary search tree
$new_node = new BST($value);
if ($new_node != null)
{
if ($this->root == null)
{
//When adds a first node in binary tree
$this->root = $new_node;
}
else
{
$find = $this->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
{
echo "\nMemory Overflow\n";
}
}
//Display tree element inorder form
function inorder($root)
{
if ($root != null)
{
$this->inorder($root->left);
echo " ". $root->data ."";
$this->inorder($root->right);
}
}
function is_identical($tree1, $tree2)
{
if ($tree1 == null && $tree2 == null)
{
return true;
}
else if ($tree1 != null && $tree2 != null && $tree1->data == $tree2->data)
{
return $this->is_identical($tree1->left, $tree2->left) && $this->is_identical($tree1->right, $tree2->right);
}
else
{
return false;
}
}
//This function are display the result of given tree is identical tree or not
function check_identical($tree1, $tree2)
{
echo "\n Given First Tree Inorder Data \n";
$this->inorder($tree1->root);
echo "\n Given Second Tree Inorder Data \n";
$this->inorder($tree2->root);
if ($this->is_identical($tree1->root, $tree2->root) == true)
{
echo "\n Is Identical Tree\n";
}
else
{
echo "\n Is not Identical Tree\n";
}
}
}
function main()
{
$tree1 = new BinarySearchTree();
$tree2 = new BinarySearchTree();
$tree3 = new BinarySearchTree();
$obj = new BinarySearchTree();
//Add first tree node
$tree1->add(7);
$tree1->add(4);
$tree1->add(11);
$tree1->add(2);
$tree1->add(5);
$tree1->add(15);
$tree1->add(3);
$tree1->add(13);
//Add second tree node
$tree2->add(7);
$tree2->add(4);
$tree2->add(11);
$tree2->add(2);
$tree2->add(5);
$tree2->add(15);
$tree2->add(3);
$tree2->add(13);
$tree2->add(17);
//Add third tree node
$tree3->add(7);
$tree3->add(4);
$tree3->add(11);
$tree3->add(2);
$tree3->add(5);
$tree3->add(15);
$tree3->add(3);
$tree3->add(13);
//Test Case
$obj->check_identical($tree1, $tree2);
$obj->check_identical($tree1, $tree3);
$obj->check_identical($tree2, $tree3);
}
main();Output
Given First Tree Inorder Data
2 3 4 5 7 11 13 15
Given Second Tree Inorder Data
2 3 4 5 7 11 13 15 17
Is not Identical Tree
Given First Tree Inorder Data
2 3 4 5 7 11 13 15
Given Second Tree Inorder Data
2 3 4 5 7 11 13 15
Is Identical Tree
Given First Tree Inorder Data
2 3 4 5 7 11 13 15 17
Given Second Tree Inorder Data
2 3 4 5 7 11 13 15
Is not Identical Tree/*
Node Js Program
Determine whether given two BST are identical or not
*/
//Tree node
class BST
{
constructor(data)
{
//Set data value of binary tree node
this.data = data;
this.left = null;
this.right = null;
}
}
class BinarySearchTree
{
constructor()
{
this.root = null;
}
//insert a node in BST
add(value)
{
//Create a dynamic node of binary search tree
var new_node = new BST(value);
if (new_node != null)
{
if (this.root == null)
{
//When adds a first node in binary tree
this.root = new_node;
}
else
{
var find = this.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
{
process.stdout.write("\nMemory Overflow\n");
}
}
//Display tree element inorder form
inorder(root)
{
if (root != null)
{
this.inorder(root.left);
process.stdout.write(" " + root.data + "");
this.inorder(root.right);
}
}
is_identical(tree1, tree2)
{
if (tree1 == null && tree2 == null)
{
return true;
}
else if (tree1 != null && tree2 != null && tree1.data == tree2.data)
{
return this.is_identical(tree1.left, tree2.left) && this.is_identical(tree1.right, tree2.right);
}
else
{
return false;
}
}
//This function are display the result of given tree is identical tree or not
check_identical(tree1, tree2)
{
process.stdout.write("\n Given First Tree Inorder Data \n");
this.inorder(tree1.root);
process.stdout.write("\n Given Second Tree Inorder Data \n");
this.inorder(tree2.root);
if (this.is_identical(tree1.root, tree2.root) == true)
{
process.stdout.write("\n Is Identical Tree\n");
}
else
{
process.stdout.write("\n Is not Identical Tree\n");
}
}
}
function main()
{
var tree1 = new BinarySearchTree();
var tree2 = new BinarySearchTree();
var tree3 = new BinarySearchTree();
var obj = new BinarySearchTree();
/*
7
/ \
4 11
/ \ \
2 5 15
\ /
3 13
*/
//Add first tree node
tree1.add(7);
tree1.add(4);
tree1.add(11);
tree1.add(2);
tree1.add(5);
tree1.add(15);
tree1.add(3);
tree1.add(13);
/*
7
/ \
4 11
/ \ \
2 5 15
\ / \
3 13 17
*/
//Add second tree node
tree2.add(7);
tree2.add(4);
tree2.add(11);
tree2.add(2);
tree2.add(5);
tree2.add(15);
tree2.add(3);
tree2.add(13);
tree2.add(17);
/*
7
/ \
4 11
/ \ \
2 5 15
\ /
3 13
*/
//Add third tree node
tree3.add(7);
tree3.add(4);
tree3.add(11);
tree3.add(2);
tree3.add(5);
tree3.add(15);
tree3.add(3);
tree3.add(13);
//Test Case
obj.check_identical(tree1, tree2);
obj.check_identical(tree1, tree3);
obj.check_identical(tree2, tree3);
}
main();Output
Given First Tree Inorder Data
2 3 4 5 7 11 13 15
Given Second Tree Inorder Data
2 3 4 5 7 11 13 15 17
Is not Identical Tree
Given First Tree Inorder Data
2 3 4 5 7 11 13 15
Given Second Tree Inorder Data
2 3 4 5 7 11 13 15
Is Identical Tree
Given First Tree Inorder Data
2 3 4 5 7 11 13 15 17
Given Second Tree Inorder Data
2 3 4 5 7 11 13 15
Is not Identical Tree# Python 3 Program
# Determine whether given two BST are identical or not
# Tree node
class BST :
def __init__(self, data) :
# Set data value of binary tree node
self.data = data
self.left = None
self.right = None
class BinarySearchTree :
def __init__(self) :
self.root = None
# insert a node in BST
def add(self, value) :
# Create a dynamic node of binary search tree
new_node = BST(value)
if (new_node != None) :
if (self.root == None) :
# When adds a first node in binary tree
self.root = new_node
else :
find = self.root
# add new node to proper position
while (find != None) :
if (find.data >= value) :
if (find.left == None) :
find.left = new_node
break
else :
# visit left sub-tree
find = find.left
else :
if (find.right == None) :
find.right = new_node
break
else :
# visit right sub-tree
find = find.right
else :
print("\nMemory Overflow\n", end = "")
# Display tree element inorder form
def inorder(self, root) :
if (root != None) :
self.inorder(root.left)
print(" ", root.data ,"", end = "")
self.inorder(root.right)
def is_identical(self, tree1, tree2) :
if (tree1 == None and tree2 == None) :
return True
elif(tree1 != None and tree2 != None and tree1.data == tree2.data) :
return (self.is_identical(tree1.left, tree2.left) and
self.is_identical(tree1.right, tree2.right))
else :
return False
# This function are display the result of given tree is identical tree or not
def check_identical(self, tree1, tree2) :
print("\n Given First Tree Inorder Data \n", end = "")
self.inorder(tree1.root)
print("\n Given Second Tree Inorder Data \n", end = "")
self.inorder(tree2.root)
if (self.is_identical(tree1.root, tree2.root) == True) :
print("\n Is Identical Tree\n", end = "")
else :
print("\n Is not Identical Tree\n", end = "")
def main() :
tree1 = BinarySearchTree()
tree2 = BinarySearchTree()
tree3 = BinarySearchTree()
obj = BinarySearchTree()
#
# 7
# / \
# 4 11
# / \ \
# 2 5 15
# \ /
# 3 13
#
# Add first tree node
tree1.add(7)
tree1.add(4)
tree1.add(11)
tree1.add(2)
tree1.add(5)
tree1.add(15)
tree1.add(3)
tree1.add(13)
#
# 7
# / \
# 4 11
# / \ \
# 2 5 15
# \ / \
# 3 13 17
#
# Add second tree node
tree2.add(7)
tree2.add(4)
tree2.add(11)
tree2.add(2)
tree2.add(5)
tree2.add(15)
tree2.add(3)
tree2.add(13)
tree2.add(17)
#
# 7
# / \
# 4 11
# / \ \
# 2 5 15
# \ /
# 3 13
#
# Add third tree node
tree3.add(7)
tree3.add(4)
tree3.add(11)
tree3.add(2)
tree3.add(5)
tree3.add(15)
tree3.add(3)
tree3.add(13)
# Test Case
obj.check_identical(tree1, tree2)
obj.check_identical(tree1, tree3)
obj.check_identical(tree2, tree3)
if __name__ == "__main__": main()Output
Given First Tree Inorder Data
2 3 4 5 7 11 13 15
Given Second Tree Inorder Data
2 3 4 5 7 11 13 15 17
Is not Identical Tree
Given First Tree Inorder Data
2 3 4 5 7 11 13 15
Given Second Tree Inorder Data
2 3 4 5 7 11 13 15
Is Identical Tree
Given First Tree Inorder Data
2 3 4 5 7 11 13 15 17
Given Second Tree Inorder Data
2 3 4 5 7 11 13 15
Is not Identical Tree# Ruby Program
# Determine whether given two BST are identical or not
# Tree node
class BST
# Define the accessor and reader of class BST
attr_reader :data, :left, :right
attr_accessor :data, :left, :right
def initialize(data)
# Set data value of binary tree node
self.data = data
self.left = nil
self.right = nil
end
end
class BinarySearchTree
# Define the accessor and reader of class BinarySearchTree
attr_reader :root
attr_accessor :root
def initialize()
@root = nil
end
# insert a node in BST
def add(value)
# Create a dynamic node of binary search tree
new_node = BST.new(value)
if (new_node != nil)
if (@root == nil)
# When adds a first node in binary tree
@root = new_node
else
find = @root
# add new node to proper position
while (find != nil)
if (find.data >= value)
if (find.left == nil)
find.left = new_node
break
else
# visit left sub-tree
find = find.left
end
else
if (find.right == nil)
find.right = new_node
break
else
# visit right sub-tree
find = find.right
end
end
end
end
else
print("\nMemory Overflow\n")
end
end
# Display tree element inorder form
def inorder(root)
if (root != nil)
self.inorder(root.left)
print(" ", root.data ,"")
self.inorder(root.right)
end
end
def is_identical(tree1, tree2)
if (tree1 == nil && tree2 == nil)
return true
elsif(tree1 != nil && tree2 != nil && tree1.data == tree2.data)
return self.is_identical(tree1.left, tree2.left) && self.is_identical(tree1.right, tree2.right)
else
return false
end
end
# This function are display the result of given tree is identical tree or not
def check_identical(tree1, tree2)
print("\n Given First Tree Inorder Data \n")
self.inorder(tree1.root)
print("\n Given Second Tree Inorder Data \n")
self.inorder(tree2.root)
if (self.is_identical(tree1.root, tree2.root) == true)
print("\n Is Identical Tree\n")
else
print("\n Is not Identical Tree\n")
end
end
end
def main()
tree1 = BinarySearchTree.new()
tree2 = BinarySearchTree.new()
tree3 = BinarySearchTree.new()
obj = BinarySearchTree.new()
#
# 7
# / \
# 4 11
# / \ \
# 2 5 15
# \ /
# 3 13
#
# Add first tree node
tree1.add(7)
tree1.add(4)
tree1.add(11)
tree1.add(2)
tree1.add(5)
tree1.add(15)
tree1.add(3)
tree1.add(13)
#
# 7
# / \
# 4 11
# / \ \
# 2 5 15
# \ / \
# 3 13 17
#
# Add second tree node
tree2.add(7)
tree2.add(4)
tree2.add(11)
tree2.add(2)
tree2.add(5)
tree2.add(15)
tree2.add(3)
tree2.add(13)
tree2.add(17)
#
# 7
# / \
# 4 11
# / \ \
# 2 5 15
# \ /
# 3 13
#
# Add third tree node
tree3.add(7)
tree3.add(4)
tree3.add(11)
tree3.add(2)
tree3.add(5)
tree3.add(15)
tree3.add(3)
tree3.add(13)
# Test Case
obj.check_identical(tree1, tree2)
obj.check_identical(tree1, tree3)
obj.check_identical(tree2, tree3)
end
main()Output
Given First Tree Inorder Data
2 3 4 5 7 11 13 15
Given Second Tree Inorder Data
2 3 4 5 7 11 13 15 17
Is not Identical Tree
Given First Tree Inorder Data
2 3 4 5 7 11 13 15
Given Second Tree Inorder Data
2 3 4 5 7 11 13 15
Is Identical Tree
Given First Tree Inorder Data
2 3 4 5 7 11 13 15 17
Given Second Tree Inorder Data
2 3 4 5 7 11 13 15
Is not Identical Tree
/*
Scala Program
Determine whether given two BST are identical or not
*/
//Tree node
class BST(var data: Int,
var left: BST,
var right: BST)
{
def this(data: Int)
{
//Set data value of binary tree node
this(data,null,null);
}
}
class BinarySearchTree(var root: BST)
{
def this()
{
this(null);
}
//insert a node in BST
def add(value: Int): Unit = {
//Create a dynamic node of binary search tree
var new_node: BST = new BST(value);
if (new_node != null)
{
if (root == null)
{
//When adds a first node in binary tree
root = new_node;
}
else
{
var find: BST = root;
//add new node to proper position
while (find != null)
{
if (find.data >= value)
{
if (find.left == null)
{
find.left = new_node;
return;
}
else
{
//visit left sub-tree
find = find.left;
}
}
else
{
if (find.right == null)
{
find.right = new_node;
return;
}
else
{
//visit right sub-tree
find = find.right;
}
}
}
}
}
else
{
print("\nMemory Overflow\n");
}
}
//Display tree element inorder form
def inorder(root: BST): Unit = {
if (root != null)
{
inorder(root.left);
print(" " + root.data + " ");
inorder(root.right);
}
}
def is_identical(tree1: BST, tree2: BST): Boolean = {
if (tree1 == null && tree2 == null)
{
return true;
}
else if (tree1 != null && tree2 != null && tree1.data == tree2.data)
{
return is_identical(tree1.left, tree2.left) && is_identical(tree1.right, tree2.right);
}
else
{
return false;
}
}
//This function are display the result of given tree is identical tree or not
def check_identical(tree1: BinarySearchTree, tree2: BinarySearchTree): Unit = {
print("\n Given First Tree Inorder Data \n");
inorder(tree1.root);
print("\n Given Second Tree Inorder Data \n");
inorder(tree2.root);
if (is_identical(tree1.root, tree2.root) == true)
{
print("\n Is Identical Tree\n");
}
else
{
print("\n Is not Identical Tree\n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree1: BinarySearchTree = new BinarySearchTree();
var tree2: BinarySearchTree = new BinarySearchTree();
var tree3: BinarySearchTree = new BinarySearchTree();
var obj: BinarySearchTree = new BinarySearchTree();
/*
7
/ \
4 11
/ \ \
2 5 15
\ /
3 13
*/
//Add first tree node
tree1.add(7);
tree1.add(4);
tree1.add(11);
tree1.add(2);
tree1.add(5);
tree1.add(15);
tree1.add(3);
tree1.add(13);
/*
7
/ \
4 11
/ \ \
2 5 15
\ / \
3 13 17
*/
//Add second tree node
tree2.add(7);
tree2.add(4);
tree2.add(11);
tree2.add(2);
tree2.add(5);
tree2.add(15);
tree2.add(3);
tree2.add(13);
tree2.add(17);
/*
7
/ \
4 11
/ \ \
2 5 15
\ /
3 13
*/
//Add third tree node
tree3.add(7);
tree3.add(4);
tree3.add(11);
tree3.add(2);
tree3.add(5);
tree3.add(15);
tree3.add(3);
tree3.add(13);
//Test Case
obj.check_identical(tree1, tree2);
obj.check_identical(tree1, tree3);
obj.check_identical(tree2, tree3);
}
}Output
Given First Tree Inorder Data
2 3 4 5 7 11 13 15
Given Second Tree Inorder Data
2 3 4 5 7 11 13 15 17
Is not Identical Tree
Given First Tree Inorder Data
2 3 4 5 7 11 13 15
Given Second Tree Inorder Data
2 3 4 5 7 11 13 15
Is Identical Tree
Given First Tree Inorder Data
2 3 4 5 7 11 13 15 17
Given Second Tree Inorder Data
2 3 4 5 7 11 13 15
Is not Identical Tree/*
Swift Program
Determine whether given two BST are identical or not
*/
//Tree node
class BST
{
var data: Int;
var left: BST? ;
var right: BST? ;
init(_ data: Int)
{
//Set data value of binary tree node
self.data = data;
self.left = nil;
self.right = nil;
}
}
class BinarySearchTree
{
var root: BST? ;
init()
{
self.root = nil;
}
//insert a node in BST
func add(_ value: Int)
{
//Create a dynamic node of binary search tree
let new_node: BST? = BST(value);
if (new_node != nil)
{
if (self.root == nil)
{
//When adds a first node in binary tree
self.root = new_node;
}
else
{
var find: BST? = self.root;
//add new node to proper position
while (find != nil)
{
if (find!.data >= value)
{
if (find!.left == nil)
{
find!.left = new_node;
break;
}
else
{
//visit left sub-tree
find = find!.left;
}
}
else
{
if (find!.right == nil)
{
find!.right = new_node;
break;
}
else
{
//visit right sub-tree
find = find!.right;
}
}
}
}
}
else
{
print("\nMemory Overflow\n", terminator: "");
}
}
//Display tree element inorder form
func inorder(_ root: BST? )
{
if (root != nil)
{
self.inorder(root!.left);
print(" ", root!.data ,"", terminator: "");
self.inorder(root!.right);
}
}
func is_identical(_ tree1: BST? , _ tree2 : BST? ) -> Bool
{
if (tree1 == nil && tree2 == nil)
{
return true;
}
else if (tree1 != nil && tree2 != nil && tree1!.data == tree2!.data)
{
return self.is_identical(tree1!.left, tree2!.left) && self.is_identical(tree1!.right, tree2!.right);
}
else
{
return false;
}
}
//This function are display the result of given tree is identical tree or not
func check_identical(_ tree1: BinarySearchTree , _ tree2 : BinarySearchTree )
{
print("\n Given First Tree Inorder Data \n", terminator: "");
self.inorder(tree1.root);
print("\n Given Second Tree Inorder Data \n", terminator: "");
self.inorder(tree2.root);
if (self.is_identical(tree1.root, tree2.root) == true)
{
print("\n Is Identical Tree\n", terminator: "");
}
else
{
print("\n Is not Identical Tree\n", terminator: "");
}
}
}
func main()
{
let tree1: BinarySearchTree = BinarySearchTree();
let tree2: BinarySearchTree = BinarySearchTree();
let tree3: BinarySearchTree = BinarySearchTree();
let obj: BinarySearchTree = BinarySearchTree();
/*
7
/ \
4 11
/ \ \
2 5 15
\ /
3 13
*/
//Add first tree node
tree1.add(7);
tree1.add(4);
tree1.add(11);
tree1.add(2);
tree1.add(5);
tree1.add(15);
tree1.add(3);
tree1.add(13);
/*
7
/ \
4 11
/ \ \
2 5 15
\ / \
3 13 17
*/
//Add second tree node
tree2.add(7);
tree2.add(4);
tree2.add(11);
tree2.add(2);
tree2.add(5);
tree2.add(15);
tree2.add(3);
tree2.add(13);
tree2.add(17);
/*
7
/ \
4 11
/ \ \
2 5 15
\ /
3 13
*/
//Add third tree node
tree3.add(7);
tree3.add(4);
tree3.add(11);
tree3.add(2);
tree3.add(5);
tree3.add(15);
tree3.add(3);
tree3.add(13);
//Test Case
obj.check_identical(tree1, tree2);
obj.check_identical(tree1, tree3);
obj.check_identical(tree2, tree3);
}
main();Output
Given First Tree Inorder Data
2 3 4 5 7 11 13 15
Given Second Tree Inorder Data
2 3 4 5 7 11 13 15 17
Is not Identical Tree
Given First Tree Inorder Data
2 3 4 5 7 11 13 15
Given Second Tree Inorder Data
2 3 4 5 7 11 13 15
Is Identical Tree
Given First Tree Inorder Data
2 3 4 5 7 11 13 15 17
Given Second Tree Inorder Data
2 3 4 5 7 11 13 15
Is not Identical Tree
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