TheDeveloperBlog.com

Home | Contact Us

C-Sharp | Java | Python | Swift | GO | WPF | Ruby | Scala | F# | JavaScript | SQL | PHP | Angular | HTML

Program to Determine Whether two Trees are Identical

Program to Determine Whether two Trees are Identical on fibonacci, factorial, prime, armstrong, swap, reverse, search, sort, stack, queue, array, linkedlist, tree, graph etc.

<< Back to PROGRAM

Q. Program to determine whether two trees are identical.

Explanation

In this program, we need to check whether two trees are identical or not. For two trees to be identical, they have to satisfy two conditions:

  1. Structure of both the trees should be the same.
  2. Nodes present in one tree should be present in another tree.
Program to determine whether two trees are identical

Above diagram contains three trees namely A, B, and C. Trees A and B are the identical as they are structurally same and values of all nodes are the same. However, trees A and C are structurally same but not identical as nodes are different in both the trees.

Algorithm

  1. Define Node class which has three attributes namely: data left and right. Here, left represents the left child of the node and right represents the right child of the node.
  2. When a node is created, data will pass to data attribute of the node and both left and right will be set to null.
  3. Define another class which has an attribute root.
    1. Root represents the root node of the tree and initializes it to null.
  4. areIdenticalTrees() will check whether two trees are identical or not:
    1. If root nodes of both the trees are null then, they are identical.
    2. If the root node of only one tree is null then, trees are not identical, return false.
    3. If root node of none of the tree is null, then check whether data of both the nodes are equal and then recursively check the left subtree and right subtree of one tree is identical to another or not.

Solution

Python

#Represent a node of binary tree
class Node:
    def __init__(self,data):
        #Assign data to the new node, set left and right children to None
        self.data = data;
        self.left = None;
        self.right = None;
 
class IdenticalTrees:
    def __init__(self):
        #Represent the root of binary tree
        self.root = None;
        
    #areIdenticalTrees() finds whether two trees are identical or not
    @staticmethod
    def areIdenticalTrees(root1, root2):
        #Checks if both the trees are empty
        if(root1 == None and root2 == None):
            return True;
        #Trees are not identical if root of only one tree is null thus, return false
        if(root1 == None and root2 == None):
            return True;
        #If both trees are not empty, check whether the data of the nodes is equal
        #Repeat the steps for left subtree and right subtree
        if(root1 != None  and root2 != None):
            return ((root1.data == root2.data) and 
            (IdenticalTrees.areIdenticalTrees(root1.left, root2.left)) and 
            (IdenticalTrees.areIdenticalTrees(root1.right, root2.right)));
        return False;
        
#Adding nodes to the first binary tree
bt1 = IdenticalTrees();
bt1.root = Node(1);
bt1.root.left = Node(2);
bt1.root.right = Node(3);
bt1.root.left.left = Node(4);
bt1.root.right.left = Node(5);
bt1.root.right.right = Node(6);
 
#Adding nodes to the second binary tree
bt2 = IdenticalTrees();
bt2.root = Node(1);
bt2.root.left = Node(2);
bt2.root.right = Node(3);
bt2.root.left.left = Node(4);
bt2.root.right.left = Node(5);
bt2.root.right.right = Node(6);  
 
#Displays whether both the trees are identical or not
if(IdenticalTrees.areIdenticalTrees(bt1.root, bt2.root)):
    print("Both the binary trees are identical");
else:
    print("Both the binary trees are not identical");

Output:

Both the binary trees are identical

C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
 
//Represent a node of binary tree
struct node{
    int data;
    struct node *left;
    struct node *right;
};
 
//Represent the root node of first binary tree
struct node *rootTree1 = NULL;
//Represent the root node of second binary tree
struct node *rootTree2 = NULL;
    
//createNode() will create a new node
struct node* createNode(int data){
    //Create a new node
    struct node *newNode = (struct node*)malloc(sizeof(struct node));
    //Assign data to newNode, set left and right children to NULL
    newNode->data= data;
    newNode->left = NULL;
    newNode->right = NULL;
    
    return newNode;
}
 
//areIdenticalTrees() finds whether two trees are identical or not
bool areIdenticalTrees(struct node *root1, struct node *root2) {
      
    //Checks if both the trees are empty
    if(root1 == NULL && root2 == NULL)
          return true;
    
    //Trees are not identical if root of only one tree is null thus, return false
    if(root1 == NULL && root2 == NULL)
          return true;
    
    //If both trees are not empty, check whether the data of the nodes is equal
    //Repeat the steps for left subtree and right subtree
    if(root1 != NULL  && root2 != NULL) {
          
          return ((root1->data == root2->data) &&
                  (areIdenticalTrees(root1->left, root2->left)) &&
                  (areIdenticalTrees(root1->right, root2->right)));
    }
    return false;
}
      
 
int main()
{
    //Adding nodes to the first binary tree
    rootTree1 = createNode(1);
    rootTree1->left = createNode(2);
    rootTree1->right = createNode(3);
    rootTree1->left->left = createNode(4);
    rootTree1->right->left = createNode(5);
    rootTree1->right->right = createNode(6);
    
    //Adding nodes to the second binary tree
    rootTree2 = createNode(1);
    rootTree2->left = createNode(2);
    rootTree2->right = createNode(3);
    rootTree2->left->left = createNode(4);
    rootTree2->right->left = createNode(5);
    rootTree2->right->right = createNode(6);  
    
    //Displays whether both the trees are identical or not
    if(areIdenticalTrees(rootTree1, rootTree2))
        printf("Both the binary trees are identical");
    else
        printf("Both the binary trees are not identical");
 
    return 0;
}

Output:

Both the binary trees are identical

JAVA

public class IdenticalTrees {
    
      //Represent the node of the binary tree
      public static class Node{
        int data;
        Node left;
        Node right;
        
        //Assign data to the new node, set left and right children to null
        public Node(int data){
          this.data = data;
          this.left = null;
          this.right = null;
        }
      }
      
      //Represent the root of the binary tree
      public Node root;
      
      public IdenticalTrees(){
        root = null;
      }
      
      //areIdenticalTrees() finds whether two trees are identical or not
      public static boolean areIdenticalTrees(Node root1, Node root2) {
          
          //Checks if both the trees are empty
          if(root1 == null && root2 == null)
              return true;
          
          //Trees are not identical if root of only one tree is null thus, return false
          if(root1 == null && root2 == null)
              return true;
          
          //If both trees are not empty, check whether the data of the nodes is equal
          //Repeat the steps for left subtree and right subtree
          if(root1 != null  && root2 != null) {
              
              return ((root1.data == root2.data) &&
                      (areIdenticalTrees(root1.left, root2.left)) &&
                      (areIdenticalTrees(root1.right, root2.right)));
          }
          return false;
      }
      
      
      public static void main(String[] args) {
        
        //Adding nodes to the first binary tree
        IdenticalTrees bt1 = new IdenticalTrees();
        bt1.root = new Node(1);
        bt1.root.left = new Node(2);
        bt1.root.right = new Node(3);
        bt1.root.left.left = new Node(4);
        bt1.root.right.left = new Node(5);
        bt1.root.right.right = new Node(6);
        
        //Adding nodes to the second binary tree
          IdenticalTrees bt2 = new IdenticalTrees();
          bt2.root = new Node(1);
          bt2.root.left = new Node(2);
          bt2.root.right = new Node(3);
          bt2.root.left.left = new Node(4);
          bt2.root.right.left = new Node(5);
          bt2.root.right.right = new Node(6);  
          
          //Displays whether both the trees are identical or not
           if(areIdenticalTrees(bt1.root, bt2.root))
             System.out.println("Both the binary trees are identical");
         else
             System.out.println("Both the binary trees are not identical");
        }
}

Output:

Both the binary trees are identical

C#

using System;
namespace Tree 
{                     
    public class Program
    {
        //Represent a node of binary tree
        public class Node<T>{
            public T data;
            public Node<T> left;
            public Node<T> right;
            
            public Node(T data) {
                //Assign data to the new node, set left and right children to null
                this.data = data;
                this.left = null;
                this.right = null;
            }
        }
        
        public class IdenticalTrees<T>{
            //Represent the root of binary tree
            public Node<T> root;
            
            public IdenticalTrees(){
                root = null;
            }
            
        //areIdenticalTrees() finds whether two trees are identical or not
        public static Boolean areIdenticalTrees(Node<T> root1, Node<T> root2) {
          
          //Checks if both the trees are empty
          if(root1 == null && root2 == null)
              return true;
          
          //Trees are not identical if root of only one tree is null thus, return false
          if(root1 == null && root2 == null)
              return true;
          
          //If both trees are not empty, check whether the data of the nodes is equal
          //Repeat the steps for left subtree and right subtree
          if(root1 != null  && root2 != null) {
              
              return ((root1.data.Equals(root2.data)) &&
                      (areIdenticalTrees(root1.left, root2.left)) &&
                      (areIdenticalTrees(root1.right, root2.right)));
          }
          return false;
        }
    }
        
        public static void Main()
        {
            //Adding nodes to the first binary tree
            IdenticalTrees<int> bt1 = new IdenticalTrees<int>();
            bt1.root = new Node<int>(1);
            bt1.root.left = new Node<int>(2);
            bt1.root.right = new Node<int>(3);
            bt1.root.left.left = new Node<int>(4);
            bt1.root.right.left = new Node<int>(5);
            bt1.root.right.right = new Node<int>(6);
            
            //Adding nodes to the second binary tree
              IdenticalTrees<int> bt2 = new IdenticalTrees<int>();
              bt2.root = new Node<int>(1);
              bt2.root.left = new Node<int>(2);
              bt2.root.right = new Node<int>(3);
              bt2.root.left.left = new Node<int>(4);
              bt2.root.right.left = new Node<int>(5);
              bt2.root.right.right = new Node<int>(6);  
              
              //Displays whether both the trees are identical or not
               if(IdenticalTrees<int>.areIdenticalTrees(bt1.root, bt2.root))
                 Console.WriteLine("Both the binary trees are identical");
             else
                 Console.WriteLine("Both the binary trees are not identical");                
        }    
    }
}

Output:

Both the binary trees are identical

PHP

<!DOCTYPE html>
<html>
<body>
<?php
//Represent a node of binary tree
class Node{
    public $data;
    public $left;
    public $right;
    
    function __construct($data){
        //Assign data to the new node, set left and right children to NULL
        $this->data = $data;
        $this->left = NULL;
        $this->right = NULL;
    }
}
class IdenticalTrees{
    //Represent the root of binary tree
    public $root;
    function __construct(){
        $this->root = NULL;
    }
    
    //areIdenticalTrees() finds whether two trees are identical or not
    static function areIdenticalTrees($root1, $root2) {
        
        //Checks if both the trees are empty
        if($root1 == NULL && $root2 == NULL)
            return true;
          
          //Trees are not identical if root of only one tree is null thus, return false
          if($root1 == NULL && $root2 == NULL)
              return true;
          
          //If both trees are not empty, check whether the data of the nodes is equal
          //Repeat the steps for left subtree and right subtree
          if($root1 != NULL  && $root2 != NULL) {
              
              return (($root1->data == $root2->data) &&
                      (IdenticalTrees::areIdenticalTrees($root1->left, $root2->left)) &&
                      (IdenticalTrees::areIdenticalTrees($root1->right, $root2->right)));
          }
          return false;
      }    
}
//Adding nodes to the first binary tree
$bt1 = new IdenticalTrees();
$bt1->root = new Node(1);
$bt1->root->left = new Node(2);
$bt1->root->right = new Node(3);
$bt1->root->left->left = new Node(4);
$bt1->root->right->left = new Node(5);
$bt1->root->right->right = new Node(6);
 
//Adding nodes to the second binary tree
$bt2 = new IdenticalTrees();
$bt2->root = new Node(1);
$bt2->root->left = new Node(2);
$bt2->root->right = new Node(3);
$bt2->root->left->left = new Node(4);
$bt2->root->right->left = new Node(5);
$bt2->root->right->right = new Node(6);  
          
//Displays whether both the trees are identical or not
if(IdenticalTrees::areIdenticalTrees($bt1->root, $bt2->root))
    print("Both the binary trees are identical");
else
    print("Both the binary trees are not identical");      
?>
</body>
</html>

Output:

Both the binary trees are identical

Next TopicPrograms List




Related Links:

.Net

.NET Array Dictionary List String 2D Async DataTable Dates DateTime Enum File For Foreach Format IEnumerable If IndexOf Lambda LINQ Parse Path Process Property Regex Replace Sort Split Static StringBuilder Substring Switch Tuple

Java

Core Array ArrayList HashMap String 2D Cast Character Console Deque Duplicates File For Format HashSet If IndexOf Lambda Math ParseInt Process Random Regex Replace Sort Split StringBuilder Substring Switch Vector While

Related Links

Adjectives Ado Ai Android Angular Antonyms Apache Articles Asp Autocad Automata Aws Azure Basic Binary Bitcoin Blockchain C Cassandra Change Coa Computer Control Cpp Create Creating C-Sharp Cyber Daa Data Dbms Deletion Devops Difference Discrete Es6 Ethical Examples Features Firebase Flutter Fs Git Go Hbase History Hive Hiveql How Html Idioms Insertion Installing Ios Java Joomla Js Kafka Kali Laravel Logical Machine Matlab Matrix Mongodb Mysql One Opencv Oracle Ordering Os Pandas Php Pig Pl Postgresql Powershell Prepositions Program Python React Ruby Scala Selecting Selenium Sentence Seo Sharepoint Software Spellings Spotting Spring Sql Sqlite Sqoop Svn Swift Synonyms Talend Testng Types Uml Unity Vbnet Verbal Webdriver What Wpf