C++ Program to Check if two trees are Identical

In this article, we will learn how to implement a program to check whether the given two trees are identical or not in C++. Two trees are said to identical when they have the same data and the arrangement of the data is also the same.

Check Whether Two Trees are Identical in C++

1. Firstly, check base condition if both trees are NULL then return 1.

2. Now check if both trees are not equal NULL then

• return true if root1->data == root2->data && identicalTree(root1->left, root2->left) && identicalTree(root1->right, root2->right)

3. For all the remaining cases return 0.

#include <bits/stdc++.h>
using namespace std;

struct Node{
    int data;
    Node* left;
    Node* right;
};
// function to create a new node
Node* newNode(int data){
    Node* node = new Node();
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}
// function return true if the given trees are identical else returns false
int identicalTree(Node* root1, Node* root2){
    if (root1 == NULL && root2 == NULL)
        return 1;
    if (root1 != NULL && root2 != NULL){
        return (root1->data == root2->data &&
                identicalTree(root1->left, root2->left) &&
                identicalTree(root1->right, root2->right));
    }
    return 0;
}
int main(){
    // tree 1
    Node* root1 = newNode(1);
    root1->right = newNode(2);
    root1->left = newNode(3);
    root1->right->left = newNode(4);
    root1->right->right = newNode(5);
    root1->left->right = newNode(6);
    root1->left->right = newNode(7);

    // tree 2
    Node* root2 = newNode(1);
    root2->right = newNode(2);
    root2->left = newNode(3);
    root2->right->left = newNode(4);
    root2->right->right = newNode(5);
    root2->left->right = newNode(6);
    root2->left->right = newNode(7);
    if(identicalTree(root1, root2))
        cout<<"Identical Trees"<<endl;
    else
        cout<<"Non identical trees"<<endl;
}

Output

Identical Trees

Also, read

• Check if two nodes are cousins in a Binary Tree in C++
• C++ program to Check if two trees are Mirror