POTD Solutions | 21 Nov’ 23 | Determine if Two Trees are Identical
Welcome to the daily solutions of our PROBLEM OF THE DAY (POTD). We will discuss the entire problem step-by-step and work towards developing an optimized solution. This will not only help you brush up on your concepts of Binary Tree but will also help you build up problem-solving skills.
POTD 21 November: Determine if Two Trees are Identical:
Given two binary trees, the task is to find if both of them are identical or not. Return true if they are identical, else return false.
Examples:
Input: 1 1
/ \ / \
2 3 2 3
/ /
4 4
Output: Yes
Explanation: Both trees are identical as the have same root, left and right child.Input: 1 1
/ \ / \
2 3 5 3
/ /
4 4
Output: Trees are not identical
Determine if two trees are identical using Morris Traversal:
The basic idea behind the Morris traversal approach to solve the problem of checking if two binary trees are identical is to use the Morris traversal algorithm to traverse both trees in-order simultaneously, and compare the nodes visited at each step.
Follow the steps to implement the above idea:
- Check if both trees are empty. If they are, return true. If only one of them is empty, return false.
- Perform the Morris traversal for in-order traversal of both trees simultaneously. At each step, compare the nodes visited in both trees.
- If at any step, the nodes visited in both trees are not equal, return false.
- If we reach the end of both trees simultaneously (i.e., both nodes are NULL), return true.
Below is the implementation of the above idea:
C++
class Solution { public : // Function to check if two trees are identical. bool isIdentical(Node* r1, Node* r2) { // Base cases // both trees are empty if (r1 == NULL && r2 == NULL) return true ; // one of the trees is empty, which means they are // not identical if (r1 == NULL || r2 == NULL) return false ; // Morris traversal while (r1 != NULL && r2 != NULL) { // if the data of the current nodes is not the // same, then the trees are not identical if (r1->data != r2->data) return false ; // Morris traversal for r1 // if the left child is NULL, move to the right // child if (r1->left == NULL) { r1 = r1->right; } else { // if the left child is not NULL, find the // predecessor Node* pre = r1->left; // find the rightmost node in the left // subtree while (pre->right != NULL && pre->right != r1) pre = pre->right; if (pre->right == NULL) { // if the right pointer of the // predecessor is NULL, make it point to // the current node pre->right = r1; r1 = r1->left; } else { // if the right pointer of the // predecessor is already pointing to // the current node, set it back to NULL // and move to the right child pre->right = NULL; r1 = r1->right; } } // Morris traversal for r2, same as for r1 if (r2->left == NULL) { r2 = r2->right; } else { Node* pre = r2->left; while (pre->right != NULL && pre->right != r2) pre = pre->right; if (pre->right == NULL) { pre->right = r2; r2 = r2->left; } else { pre->right = NULL; r2 = r2->right; } } } // if both r1 and r2 are NULL, then the trees are // identical return (r1 == NULL && r2 == NULL); } }; |
Java
class Solution { // Function to check if two trees are identical. boolean isIdentical(Node root1, Node root2) { // both trees are empty if (root1 == null && root2 == null ) return true ; // // one of the trees is empty, which means they // are not identical if (root1 == null || root2 == null ) return false ; // Morris traversal // if the data of the current nodes is not the same, // then the trees are not identical while (root1 != null && root2 != null ) { if (root1.data != root2.data) return false ; // Morris traversal for root1 // if the left child is NULL, move to the right // child if (root1.left == null ) { root1 = root1.right; } else { // if the left child is not NULL, find the // predecessor Node pre = root1.left; // find the rightmost node in the left // subtree while (pre.right != null && pre.right != root1) pre = pre.right; // if the right pointer of the predecessor // is NULL, make it point to the current // node if (pre.right == null ) { pre.right = root1; root1 = root1.left; } else { // if the right pointer of the // predecessor is already pointing to // the current node, set it back to NULL // and move to the right child pre.right = null ; root1 = root1.right; } } // Morris traversal for root2, same as for root1 if (root2.left == null ) { root2 = root2.right; } else { Node pre = root2.left; while (pre.right != null && pre.right != root2) pre = pre.right; if (pre.right == null ) { pre.right = root2; root2 = root2.left; } else { pre.right = null ; root2 = root2.right; } } } // if both root1 and root2 are NULL, then the trees are // identical return (root1 == null && root2 == null ); } } |
Python3
class Solution: # Function to check if two trees are identical. def isIdentical( self , root1, root2): # Base cases # both trees are empty if not root1 and not root2: return True # one of the trees is empty, which means they are not identical if not root1 or not root2: return False # Morris traversal while root1 and root2: # if the data of the current nodes is not the same, then the trees are not identical if root1.data ! = root2.data: return False # Morris traversal for root1 # if the left child is None, move to the right child if not root1.left: root1 = root1.right # if the left child is not None, find the predecessor else : pre = root1.left # find the rightmost node in the left subtree while pre.right and pre.right ! = root1: pre = pre.right if not pre.right: # if the right pointer of the predecessor is None, make it point to the current node pre.right = root1 root1 = root1.left else : # if the right pointer of the predecessor is already pointing to the current node, set it back to None and move to the right child pre.right = None root1 = root1.right # Morris traversal for root2, same as for root1 if not root2.left: root2 = root2.right else : pre = root2.left while pre.right and pre.right ! = root2: pre = pre.right if not pre.right: pre.right = root2 root2 = root2.left else : pre.right = None root2 = root2.right # if both root1 and root2 are None, then the trees are identical return not root1 and not root2 |
Time Complexity: O(N), where N is the number of nodes in the binary tree
Auxiliary Space: O(1)