Skip to main content

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




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.

New Comment