Check if two binary tree are identical

In this chapter, we shall see if 2 trees are identical.

Problem statement:

You are given root node of 2 binary trees, you need to check if 2 trees are identical.

Example:

Consider the below image

The first set are identical; the second set are not identical.

From the image we can derive below true cases:

1. If both nodes are null, then return true
2. If the right node value of tree 1 is equal to the right node value of tree 2, return true.
3. If the Left node value of tree 1 is equal to the Left node value of tree 2, return true.

From the image we can derive below false cases:

1. If a node from tree 1 has value, and node from tree 2 is null, then return false.
2. If both the tree nodes have a value, but they are different, then return false.

Solution in C++

#include <iostream>
#include <stack>
#include <map>
using namespace std;

// structure to hold binary tree node
struct Node
{
    int data;
    Node *left, *right;

    Node(int data)
    {
        this->data = data;
        this->left = this->right = nullptr;
    }
};

int check_is_identical(Node* root1, Node* root2) 
{ 
    if (root1 == NULL && root2 == NULL) 
        return 1; 

    else if (root1 != NULL && root2 == NULL) 
        return 0; 
    else if (root1 == NULL && root2 != NULL) 
        return 0; 
    else { 
        if (root1->data == root2->data && check_is_identical(root1->left, root2->left) 
            && check_is_identical(root1->right, root2->right)) 
            return 1; 
        else
            return 0; 
    } 
} 
  
  
  
int main()  
{  
    Node* root = nullptr;
    /* Binary tree:
              16
            /   \
           /     \
          10      25
         /  \    /  \
        /    \  /    \
       7    15 18     30

    */

    root = new Node(16);
    root->left = new Node(10);
    root->right = new Node(25);
    root->left->left = new Node(7);
    root->left->right = new Node(15);
    root->right->left = new Node(18);
    root->right->right = new Node(30);

    Node* root_1 = nullptr;
    /* Binary tree:
              16
            /   \
           /     \
          25      10
         /  \    /  \
        /    \  /    \
       30    18 15     7

    */

    root_1 = new Node(16);
    root_1->left = new Node(25);
    root_1->right = new Node(10);
    root_1->left->left = new Node(30);
    root_1->left->right = new Node(18);
    root_1->right->left = new Node(15);
    root_1->right->right = new Node(7);

    if(check_is_identical(root, root_1))
    {
        cout<<"Both of them are identical"<<endl;
    } else {
        cout<<"Both of them are not identical"<<endl;
    }

    return 0;  
}

Output:

Both of them are not identical

List Of Tutorials available in this website: