How to Check If Two Binary Trees are Identical.
Given two binary trees, write a code to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical and the nodes have the same value.
For example: (Check the image)
Example 1: true
In this first example, Both the trees are same. They have the same structure as well as their node values are same.
Example 2: false
In the second example, Both the trees are structurally same but the value of left children of tree A is not equal to tree B.
Example 3: false
Both the trees are structurally not identical.
In this tutorial, I am going to discuss iterative and recursive approach to solve this problem. At the end of this post i have shared a video tutorial link in which i have explained both the approaches.
Programming questions on binary trees
Check If Two Binary Trees are Identical using Level Order Traversal – Java Code
In this example, we are going to solve this problem using Level Order Traversal. We traverse both the trees level by level simultaneously and compare the nodes value.
If both the trees are same then it means both have same structure as well as their node values are same.
The time and space complexity of this approach is O(n).
|
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 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
//Same Tree using Level Order Traversal public class SameTree { public static boolean isSame(TreeNode p, TreeNode q) { //If both the trees are empty, then return true if(p == null && q == null) { return true; } else if(p == null || q == null) { return false; } //Declare two queues Queue<TreeNode> qu1 = new LinkedList<>(); Queue<TreeNode> qu2 = new LinkedList<>(); qu1.add(p); qu2.add(q); while(!qu1.isEmpty() && !qu2.isEmpty()) { TreeNode temp1 = qu1.poll(); TreeNode temp2 = qu2.poll(); //If node value is not same if(temp1.data != temp2.data) { return false } //Add left children if(temp1.left != null && temp2.left != null) { qu1.add(temp1.left) qu2.add(temp2.left); } else if(temp1.left != null || temp2.left != null) { return false; } //Add right children if(temp1.right != null && temp2.right != null) { qu1.add(temp1.right); qu2.add(temp2.right); } else if(temp1.right != null || temp2.right != null){ return false; } } return true; } public static void main(String[] args) { TreeNode root1 = createFirstTree(); TreeNode root2 = createSecondTree(); boolean result = isSame(root1, root2); System.out.println(result); } public static class TreeNode { int data; TreeNode left; TreeNode right; TreeNode(int data) { this.data = data; } } public static TreeNode createFirstTree() { TreeNode rootNode = new TreeNode(1); rootNode.left = new TreeNode(2); rootNode.right = new TreeNode(3); return rootNode; } public static TreeNode createSecondTree() { TreeNode rootNode = new TreeNode(1); rootNode.left = new TreeNode(2); rootNode.right = new TreeNode(3); return rootNode; } } |
Check If Two Trees are Identical using Recursion – Java Code
In the last example, we have solved this problem using iterative approach. Let’s see how we can solve this problem using recursion.
To solve this problem using recursion, we have to check these three conditions in each recursive call.
i) If both the trees are empty then return true.
ii) Else if any of the tree is empty and other is not then return false.
iii) Else if data of both the nodes are not same then return false.
The time complexity of this approach is O(n).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
//Check If Two Trees are Identical using Recursion public static boolean isSame(TreeNode p, TreeNode q) { if(p == null && q == null) { return true; } else if(p == null || q == null) { return false; } else if(p.data != q.data) { return false; } else { return isSame(p.left, q.left) && isSame(p.right, q.right); } } |
