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); }