# How to check if two binary trees are identical ?

Companies:

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);
}
Scroll to Top

### Full Stack Integrated Bootcamp Free Trial

• Please enter a number from 7000000000 to 9999999999.