How to check if two binary trees are identical ?

Given two binary trees, write a program to check if the two binary trees are identical or not ?

Solution

We can solve the above problem recursively. If the root node of the tree is equal then we check for the equality of left subtree and right subtree.
Similarly, we check for the equality of the left subtree and right subtree by comparing the root elements of left subtree and right subtree.

Implementation

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

typedef struct node {
    int data;
    node* left;
    node* right;
} node;

node* createNewNode(int data) {
    node* newNode = new node;
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

bool checkIfEqual(node* first, node* second) {
    if (first == NULL && second == NULL) return true;
    else if (first == NULL && second != NULL) return false;
    else if (first != NULL && second == NULL) return false;
    else {
        if (first->data == second->data) {
            return checkIfEqual(first->left, second->left) && checkIfEqual(first->right, second->right);
        }
        else {
            return false;
        }
    }
}

int main() {

    // First Tree
    node* firstRoot = createNewNode(5);
    firstRoot->left = createNewNode(10);
    firstRoot->right = createNewNode(15);
    firstRoot->left->left = createNewNode(25);
    firstRoot->right->right = createNewNode(30);

    // Second Tree
    node* secondRoot = createNewNode(5);
    secondRoot->left = createNewNode(10);
    secondRoot->right = createNewNode(15);
    secondRoot->left->left = createNewNode(25);
    secondRoot->right->right = createNewNode(30);

    cout << (checkIfEqual(firstRoot, secondRoot) == true ? "Trees are equal!" : "Trees are unequal" )<< "\n";

    return (0);
}