Given the roots of two binary trees, determine if these trees are identical or not. Identical trees have the same layout and data at each node. Consider the following two identical binary trees that have the same layout and data.
It is not necessary that trees that have the same data are identical trees. Trees that have the exact same data may not be structurally identical. For example if you look at the two trees below, although they have the same data, they are not identical.
bool are_identical(BinaryTreeNode* root1,BinaryTreeNode* root2) {//TODO: Write - Your - Codereturn false;}
bool are_identical(BinaryTreeNode* root1,BinaryTreeNode* root2) {if (root1 == nullptr && root2 == nullptr) {return true;}if (root1 != nullptr && root2 != nullptr) {return ((root1->data == root2->data) &&are_identical(root1->left, root2->left) &&are_identical(root1->right, root2->right));}return false;}int main() {BinaryTreeNode *root1 = new BinaryTreeNode(100);insert_bst(root1, 50);insert_bst(root1, 200);insert_bst(root1, 25);insert_bst(root1, 125);insert_bst(root1, 350);display_level_order(root1);BinaryTreeNode *root2 = create_random_BST(15);display_level_order(root2);// Try changing the roots being passedif(are_identical(root1, root2)) {cout<< " the trees are identical" << endl;} else {cout<< "the trees are not identical" << endl;}}
Linear, O(n).
O(h)
The recursive solution has O(h) memory complexity as it will consume memory on the stack up to the height of binary tree h. It will be O(log n) for a balanced tree and in the worst case can be O(n).
This problem can be effectively solved using a recursive solution. The base case of recursion for this solution is if both nodes being compared are null, or one of them is null.
Two trees ‘A’ and ‘B’ are identical if:
To solve this problem, we’ll do a depth-first traversal on both trees simultaneously and keep comparing the data at each level.
Practice problems like this and many more by checking out our Grokking the Coding Interview: Patterns for Coding Questions course!