Write an efficient algorithm to check if two binary trees are identical or not. i.e. if they have identical structure & their contents are also same.

The idea is to traverse both trees and compare value at their root node. If the value matches, we recursively check if left subtree of first tree is identical to left subtree of second tree and right subtree of first tree is identical to right subtree of second tree. If the value at their root node differs, the trees violates data property. If at any point in the recursion, the first tree is empty & second tree is non-empty or second tree is empty & first tree is non-empty, the trees violates structural property and they cannot be identical.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Data structure to store a Binary Tree node struct Node { int key; Node *left, *right; }; // Recursive function to check if two given binary trees are // identical or not int isIdentical(Node* x, Node* y) { // if both trees are empty, return true if (x == nullptr && y == nullptr) return 1; // if both trees are non-empty and value of their root node matches, // recurse for their left and right sub-tree return (x && y) && (x->key == y->key) && isIdentical(x->left, y->left) && isIdentical(x->right, y->right); } |

#### Iterative solution –

In iterative version, we make use of stack data structure in similar way as implicit recursive stack.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
// Data structure to store a Binary Tree node struct Node { int key; Node *left, *right; }; // Iterative function to check if given binary trees are identical or not bool isIdentical(Node *x, Node *y) { // if both trees are empty, return true if (x == nullptr && y == nullptr) return true; // if first tree is empty (& second tree is non-empty), return false if (x == nullptr) return false; // if second tree is empty (& first tree is non-empty), return false if (y == nullptr) return false; // create a stack to hold Node* pairs stack<pair<Node*, Node*>> stack; stack.push({x, y}); // do till stack is not empty while (!stack.empty()) { // pop top pair from the stack and process it Node *x = stack.top().first; Node *y = stack.top().second; stack.pop(); // if value of their root node don't match, return false if (x->key != y->key) return false; // if left subtree of both x and y exists, push their addresses // to stack else return false if only one left child exists if (x->left && y->left) stack.push({x->left, y->left}); else if (x->left || y->left) return false; // if right subtree of both x and y exists, push their addresses // to stack else return false if only one right child exists if (x->right && y->right) stack.push({x->right, y->right}); else if (x->right || y->right) return false; } // if we reach here, both binary trees are identical return true; } |

The time complexity of both recursive and iterative solution is linear in terms of number of nodes in two trees.

**Thanks for reading.**

Please use our online compiler to post code in comments. To contribute, get in touch with us.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

provide one or two sample input and output. it will be help ful in understanding.

I think there is a bug in the recursive solution. returning false when one tree is null and other is not is missing