Question:
Given a binary tree root node, check if the tree is a isomorphic tree.
2 trees are called isomorphic to each other, if they have same structure or mirror structure.
And their data should also match.
Solution in C++
#include <iostream> #include <queue> #include <stack> 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; } }; bool check_if_isomorphic_tree(Node *node1, Node *node2) { if (node1 == NULL && node2 == NULL) { return true; } if (node1 == NULL || node2 == NULL) { return false; } // data should also match if (node1->data != node2->data) { return false; } // check if the structure is same or if the structure is mirror to each other return (check_if_isomorphic_tree(node1->left, node2->left) && check_if_isomorphic_tree(node1->right, node2->right)) || (check_if_isomorphic_tree(node1->left, node2->right) && check_if_isomorphic_tree(node1->right, node2->left)); } 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_if_isomorphic_tree(root, root_1)) { cout<<"Tree is a isomorphic tree"<<endl; } else { cout<<"Tree is Not a isomorphic tree"<<endl; } return 0; }
Output:
Tree is a isomorphic tree