Intuition :
We can simply solve this question using recursion. For this we have to declare the base case i.e. if(root1 == null && root2 == null) return true;
Approach :
1. Define Base Cases:
- Both Trees are Empty: If both trees are null, they are identical. Return true.
- One Tree is Empty: If one tree is null and the other is not, they cannot be identical. Return false.
2. Compare Current Nodes:
- Check if the values of the current nodes in both trees are equal. If they are not, return false.
3. Recursive Checks:
- If the current nodes are equal, recursively check:
- Left Subtrees: Call the function on the left child of both trees.
- Right Subtrees: Call the function on the right child of both trees.
- Combine the results of these two recursive calls using a logical AND operator (&&). Both calls must return true for the trees to be considered identical.
4. Return Result:
- If all checks are passed, return true. If any check fails, return false.
Pseudocode:
function areIdentical(tree1, tree2):
if tree1 is NULL and tree2 is NULL:
return true
if tree1 is NULL or tree2 is NULL:
return false
if tree1.value != tree2.value:
return false
return areIdentical(tree1.left, tree2.left) AND
areIdentical(tree1.right, tree2.right)
Code :
C++ Code
bool identicalTrees(BinaryTreeNode<int>* root1, BinaryTreeNode<int>* root2) {
// Write your code here.
if(root1==nullptr && root2==nullptr)return true;
if(root1==nullptr || root2==nullptr)return false;
return (root1->data == root2->data)&&
identicalTrees(root1->left, root2->left)&&
identicalTrees(root1->right, root2->right);
}
Java Code :
public class Solution {
public static boolean identicalTrees(BinaryTreeNode<Integer> root1, BinaryTreeNode<Integer> root2) {
// Write you code here.
if(root1==null && root2==null)return true;
if(root1==null || root2==null)return false;
return (root1.data == root2.data)&&
identicalTrees(root1.left, root2.left)&&
identicalTrees(root1.right, root2.right);
}
}
