Write a function to determine if two trees are identical or not:
Two trees are identical when they have the same data and the arrangement of data is also the same
Examples:
Input: 1 1
/ \ / \
2 3 2 3
/ /
4 4Output: Both trees are identical
Input: 1 1
/ \ / \
2 3 5 3
/ /
4 4Output: Trees are not identical
Approach: To solve the problem follow the below idea:
To identify if two trees are identical, we need to traverse both trees simultaneously, and while traversing we need to compare data and children of the trees
Follow the given steps to solve the problem:
- If both trees are empty then return 1(Base case)
- Else If both trees are non-empty
- Check data of the root nodes (tree1->data == tree2->data)
- Check left subtrees recursively
- Check right subtrees recursively
- If the above three statements are true then return 1
- Else return 0 (one is empty and the other is not)
Below is the implementation of this approach:
C++
// C++ program to see if two trees are identical#include <bits/stdc++.h>using namespace std;/* A binary tree node has data, pointer to left childand a pointer to right child */class node {public: int data; node* left; node* right;};/* Helper function that allocates a new node with thegiven data and NULL left and right pointers. */node* newNode(int data){ node* Node = new node(); Node->data = data; Node->left = NULL; Node->right = NULL; return (Node);}/* Given two trees, return true if they arestructurally identical */int identicalTrees(node* a, node* b){ /*1. both empty */ if (a == NULL && b == NULL) return 1; /* 2. both non-empty -> compare them */ if (a != NULL && b != NULL) { return (a->data == b->data && identicalTrees(a->left, b->left) && identicalTrees(a->right, b->right)); } /* 3. one empty, one not -> false */ return 0;}/* Driver code*/int main(){ node* root1 = newNode(1); node* root2 = newNode(1); root1->left = newNode(2); root1->right = newNode(3); root1->left->left = newNode(4); root1->left->right = newNode(5); root2->left = newNode(2); root2->right = newNode(3); root2->left->left = newNode(4); root2->left->right = newNode(5); // Function call if (identicalTrees(root1, root2)) cout << "Both trees are identical."; else cout << "Trees are not identical."; return 0;}// This code is contributed by rathbhupendra |
C
#include <stdio.h>#include <stdlib.h>/* A binary tree node has data, pointer to left child and a pointer to right child */struct node { int data; struct node* left; struct node* right;};/* Helper function that allocates a new node with the given data and NULL left and right pointers. */struct node* newNode(int data){ struct node* node = (struct node*)malloc(sizeof(struct node)); node->data = data; node->left = NULL; node->right = NULL; return (node);}/* Given two trees, return true if they are structurally identical */int identicalTrees(struct node* a, struct node* b){ /*1. both empty */ if (a == NULL && b == NULL) return 1; /* 2. both non-empty -> compare them */ if (a != NULL && b != NULL) { return (a->data == b->data && identicalTrees(a->left, b->left) && identicalTrees(a->right, b->right)); } /* 3. one empty, one not -> false */ return 0;}/* Driver code*/int main(){ struct node* root1 = newNode(1); struct node* root2 = newNode(1); root1->left = newNode(2); root1->right = newNode(3); root1->left->left = newNode(4); root1->left->right = newNode(5); root2->left = newNode(2); root2->right = newNode(3); root2->left->left = newNode(4); root2->left->right = newNode(5); // Function call if (identicalTrees(root1, root2)) printf("Both tree are identical."); else printf("Trees are not identical."); getchar(); return 0;} |
Java
// Java program to see if two trees are identical// A binary tree nodeclass Node { int data; Node left, right; Node(int item) { data = item; left = right = null; }}class BinaryTree { Node root1, root2; /* Given two trees, return true if they are structurally identical */ boolean identicalTrees(Node a, Node b) { /*1. both empty */ if (a == null && b == null) return true; /* 2. both non-empty -> compare them */ if (a != null && b != null) return (a.data == b.data && identicalTrees(a.left, b.left) && identicalTrees(a.right, b.right)); /* 3. one empty, one not -> false */ return false; } /* Driver code*/ public static void main(String[] args) { BinaryTree tree = new BinaryTree(); tree.root1 = new Node(1); tree.root1.left = new Node(2); tree.root1.right = new Node(3); tree.root1.left.left = new Node(4); tree.root1.left.right = new Node(5); tree.root2 = new Node(1); tree.root2.left = new Node(2); tree.root2.right = new Node(3); tree.root2.left.left = new Node(4); tree.root2.left.right = new Node(5); // Function call if (tree.identicalTrees(tree.root1, tree.root2)) System.out.println("Both trees are identical"); else System.out.println("Trees are not identical"); }} |
Python3
# Python3 program to determine if two trees are identical# A binary tree node has data, pointer to left child# and a pointer to right childclass Node: # Constructor to create a new node def __init__(self, data): self.data = data self.left = None self.right = None# Given two trees, return true if they are structurally# identicaldef identicalTrees(a, b): # 1. Both empty if a is None and b is None: return True # 2. Both non-empty -> Compare them if a is not None and b is not None: return ((a.data == b.data) and identicalTrees(a.left, b.left)and identicalTrees(a.right, b.right)) # 3. one empty, one not -- false return False# Driver coderoot1 = Node(1)root2 = Node(1)root1.left = Node(2)root1.right = Node(3)root1.left.left = Node(4)root1.left.right = Node(5)root2.left = Node(2)root2.right = Node(3)root2.left.left = Node(4)root2.left.right = Node(5)# Function callif __name__ == "__main__": if identicalTrees(root1, root2): print("Both trees are identical") else: print("Trees are not identical")# This code is contributed by Nikhil Kumar Singh(nickzuck_007) |
C#
// C# program to see if two trees are identicalusing System;// C# program to see if two trees are identical// A binary tree nodepublic class Node { public int data; public Node left, right; public Node(int item) { data = item; left = right = null; }}public class BinaryTree { public Node root1, root2; /* Given two trees, return true if they are structurally identical */ public virtual bool identicalTrees(Node a, Node b) { /*1. both empty */ if (a == null && b == null) { return true; } /* 2. both non-empty -> compare them */ if (a != null && b != null) { return (a.data == b.data && identicalTrees(a.left, b.left) && identicalTrees(a.right, b.right)); } /* 3. one empty, one not -> false */ return false; } /* Driver program to test identicalTrees() function */ public static void Main(string[] args) { BinaryTree tree = new BinaryTree(); tree.root1 = new Node(1); tree.root1.left = new Node(2); tree.root1.right = new Node(3); tree.root1.left.left = new Node(4); tree.root1.left.right = new Node(5); tree.root2 = new Node(1); tree.root2.left = new Node(2); tree.root2.right = new Node(3); tree.root2.left.left = new Node(4); tree.root2.left.right = new Node(5); // Function call if (tree.identicalTrees(tree.root1, tree.root2)) { Console.WriteLine("Both trees are identical"); } else { Console.WriteLine("Trees are not identical"); } }}// This code is contributed by Shrikant13 |
Javascript
<script> // JavaScript program to see if two trees are identical class Node { constructor(data) { this.left = null; this.right = null; this.data = data; } } let root1, root2; /* Given two trees, return true if they are structurally identical */ function identicalTrees(a, b) { /*1. both empty */ if (a == null && b == null) return true; /* 2. both non-empty -> compare them */ if (a != null && b != null) return (a.data == b.data && identicalTrees(a.left, b.left) && identicalTrees(a.right, b.right)); /* 3. one empty, one not -> false */ return false; } root1 = new Node(1); root1.left = new Node(2); root1.right = new Node(3); root1.left.left = new Node(4); root1.left.right = new Node(5); root2 = new Node(1); root2.left = new Node(2); root2.right = new Node(3); root2.left.left = new Node(4); root2.left.right = new Node(5); if (identicalTrees(root1, root2)) document.write("Both trees are identical"); else document.write("Trees are not identical"); </script> |
Output
Both trees are identical.
Time Complexity: O(min(N, M)), Where N and M are the sizes of the trees
Auxiliary Space: O(log min(N, M)), due to auxiliary stack space used by recursion calls
Write a function to determine if two trees are identical or not by comparing their traversals:
To solve the problem follow the below idea:
If two trees are identical, their preorder, inorder and postorder traversals will also be the same
Note: For this, we can find one traversal, say inorder, and if it is the same for both the trees, can we say the given trees are identical? No, because we can have two trees with the same inorder traversal, still they can be non-identical.
See the below example:
Tree 1: 2 Tree 2: 1
/ \
1 2Both the trees have inorder traversal as “2 1”, but they are not identical.
To tackle such edge cases, we should find all the traversal for both the trees and see if they are equal. If yes, the given trees are identical else not.
Below is the implementation of this approach:
C++
/* CPP code to check if two trees are identical */#include <bits/stdc++.h>using namespace std;/* A binary tree node */class Node {public: int data; Node* left; Node* right; Node(int d) { this->data = d; this->left = NULL; this->right = NULL; }};// Utility function to check inorder traversalvoid inOrder(Node* root, vector<int>& sol){ if (root == NULL) return; inOrder(root->left, sol); sol.push_back(root->data); inOrder(root->right, sol);}// Utility function to check preorder traversalvoid preOrder(Node* root, vector<int>& sol){ if (root == NULL) return; sol.push_back(root->data); preOrder(root->left, sol); preOrder(root->right, sol);}// Utility function to check postorder traversalvoid postOrder(Node* root, vector<int>& sol){ if (root == NULL) return; postOrder(root->left, sol); postOrder(root->right, sol); sol.push_back(root->data);}// Function to check if two trees are identicalbool isIdentical(Node* root1, Node* root2){ // Code Here // Create two vector to store traversals vector<int> res1; vector<int> res2; // check inOrder // cout<<"Hi"<<" "; inOrder(root1, res1); inOrder(root2, res2); if (res1 != res2) return false; // clear previous result to reuse vector res1.clear(); res2.clear(); // check PreOrder preOrder(root1, res1); preOrder(root2, res2); if (res1 != res2) return false; // clear previous result to reuse vector res1.clear(); res2.clear(); // check PostOrder postOrder(root1, res1); postOrder(root2, res2); if (res1 != res2) return false; return true;}// Driver codeint main(){ Node* root1 = new Node(1); root1->left = new Node(2); root1->right = new Node(3); root1->left->left = new Node(4); root1->left->right = new Node(5); Node* root2 = new Node(1); root2->left = new Node(2); root2->right = new Node(3); root2->left->left = new Node(4); root2->left->right = new Node(5); // Function call if (isIdentical(root1, root2)) { cout << "Both the trees are identical." << endl; } else { cout << "Given trees are not identical." << endl; } return 0;}// This code is contributed by adityamaharshi21 |
Java
/* java code to check if two trees are identical */import java.io.*;import java.util.*;public class GFG { /* A binary tree node */ static class Node { int data; Node left, right; public Node(int data) { this.data = data; } } // Driver code public static void main(String[] args) { Node root1 = new Node(1); root1.left = new Node(2); root1.right = new Node(3); root1.left.left = new Node(4); root1.left.right = new Node(5); Node root2 = new Node(1); root2.left = new Node(2); root2.right = new Node(3); root2.left.left = new Node(4); root2.left.right = new Node(5); // Function call if (isIdentical(root1, root2)) { System.out.println( "Both the trees are identical."); } else { System.out.println( "Given trees are not identical."); } } // Function to check if two trees are identical static boolean isIdentical(Node root1, Node root2) { // Code Here // Create two arraylist to store traversals ArrayList<Integer> res1 = new ArrayList<Integer>(); ArrayList<Integer> res2 = new ArrayList<Integer>(); // check inOrder inOrder(root1, res1); inOrder(root2, res2); if (!res1.equals(res2)) return false; // clear previous result to reuse arraylist res1.clear(); res2.clear(); // check PreOrder preOrder(root1, res1); preOrder(root2, res2); if (!res1.equals(res2)) return false; // clear previous result to reuse arraylist res1.clear(); res2.clear(); // check PostOrder postOrder(root1, res1); postOrder(root2, res2); if (!res1.equals(res2)) return false; return true; } // Utility function to check inorder traversal static void inOrder(Node root, ArrayList<Integer> sol) { if (root == null) return; inOrder(root.left, sol); sol.add(root.data); inOrder(root.right, sol); } // Utility function to check preorder traversal static void preOrder(Node root, ArrayList<Integer> sol) { if (root == null) return; sol.add(root.data); preOrder(root.left, sol); preOrder(root.right, sol); } // Utility function to check postorder traversal static void postOrder(Node root, ArrayList<Integer> sol) { if (root == null) return; postOrder(root.left, sol); postOrder(root.right, sol); sol.add(root.data); }} |
Python3
# Python program to check if two trees are identical# A binary tree nodeclass Node: def __init__(self, key): self.data = key self.left = None self.right = None# Utility function to check inorder traversal def inOrder(root, sol): if root is None: return inOrder(root.left, sol) sol.append(root.data) inOrder(root.right, sol) # Utility function to check preorder traversaldef preOrder(root, sol): if root is None: return sol.append(root.data) preOrder(root.left, sol) preOrder(root.right, sol)# Utility function to check postorder traversaldef postOrder(root, sol): if root is None: return postOrder(root.left, sol) postOrder(root.right, sol) sol.append(root.data)# Function to check if two trees are identicaldef isIdentical(root1, root2): # Code here # Create two vector to store traversal res1 = [] res2 = [] #check inorder inOrder(root1, res1) inOrder(root2, res2) if res1 != res2: return False # clear previous result to reuse vector res1.clear() res2.clear() # check PreOrder preOrder(root1, res1) preOrder(root2, res2) if res1 != res2: return False # clear previous result to reuse vector res1.clear() res2.clear() # check PostOrder postOrder(root1, res1) postOrder(root2, res2) if res1 != res2: return False return True # Driver codeif __name__ == '__main__': root1 = Node(1) root1.left = Node(2) root1.right = Node(3) root1.left.left = Node(4) root1.left.right = Node(5) root2 = Node(1) root2.left = Node(2) root2.right = Node(3) root2.left.left = Node(4) root2.left.right = Node(5) # Function Call if isIdentical(root1, root2): print("Both the trees are identical.") else: print("Given trees are not identical") # This code is contributed by Yash Agarwal(yashagarwal2852002) |
C#
/* C# code to check if two trees are identical */using System;using System.Collections.Generic;public class GFG { /* A binary tree node */ class Node { public int data; public Node left, right; public Node(int data) { this.data = data; } } // Driver code public static void Main(String[] args) { Node root1 = new Node(1); root1.left = new Node(2); root1.right = new Node(3); root1.left.left = new Node(4); root1.left.right = new Node(5); Node root2 = new Node(1); root2.left = new Node(2); root2.right = new Node(3); root2.left.left = new Node(4); root2.left.right = new Node(5); // Function call if (isIdentical(root1, root2)) { Console.WriteLine( "Both the trees are identical."); } else { Console.WriteLine( "Given trees are not identical."); } } // Function to check if two trees are identical static bool isIdentical(Node root1, Node root2) { // Code Here // Create two arraylist to store traversals List<int> res1 = new List<int>(); List<int> res2 = new List<int>(); // check inOrder inOrder(root1, res1); inOrder(root2, res2); if (!res1.Equals(res2)) return false; // clear previous result to reuse arraylist res1.Clear(); res2.Clear(); // check PreOrder preOrder(root1, res1); preOrder(root2, res2); if (!res1.Equals(res2)) return false; // clear previous result to reuse arraylist res1.Clear(); res2.Clear(); // check PostOrder postOrder(root1, res1); postOrder(root2, res2); if (!res1.Equals(res2)) return false; return true; } // Utility function to check inorder traversal static void inOrder(Node root, List<int> sol) { if (root == null) return; inOrder(root.left, sol); sol.Add(root.data); inOrder(root.right, sol); } // Utility function to check preorder traversal static void preOrder(Node root, List<int> sol) { if (root == null) return; sol.Add(root.data); preOrder(root.left, sol); preOrder(root.right, sol); } // Utility function to check postorder traversal static void postOrder(Node root, List<int> sol) { if (root == null) return; postOrder(root.left, sol); postOrder(root.right, sol); sol.Add(root.data); }}// This code is contributed adityamaharshi21 |
Javascript
// JavaScript program for above approachclass Node { constructor(d) { this.data = d; this.left = null; this.right = null; }}// Utility function to check inorder traversalfunction inOrder(root, sol) { if (root == null) return; inOrder(root.left, sol); sol.push(root.data); inOrder(root.right, sol);}// Utility function to check preorder traversalfunction preOrder(root, sol) { if (root == null) return; sol.push(root.data); preOrder(root.left, sol); preOrder(root.right, sol);}// Utility function to check postorder traversalfunction postOrder(root, sol) { if (root == null) return; postOrder(root.left, sol); postOrder(root.right, sol); sol.push(root.data);}// Function to check if two trees are identicalfunction isIdentical(root1, root2) { // Code Here // Create two vector to store traversals let res1 = []; let res2 = []; // check inOrder inOrder(root1, res1); inOrder(root2, res2); if (res1.toString() != res2.toString()) return false; // clear previous result to reuse vector res1 = []; res2 = []; // check PreOrder preOrder(root1, res1); preOrder(root2, res2); if (res1.toString() != res2.toString()) return false; // clear previous result to reuse vector res1 = []; res2 = []; // check PostOrder postOrder(root1, res1); postOrder(root2, res2); if (res1.toString() != res2.toString()) return false; return true;}// Driver codelet root1 = new Node(1);root1.left = new Node(2);root1.right = new Node(3);root1.left.left = new Node(4);root1.left.right = new Node(5);let root2 = new Node(1);root2.left = new Node(2);root2.right = new Node(3);root2.left.left = new Node(4);root2.left.right = new Node(5);// Function callif (isIdentical(root1, root2)) { console.log("Both the trees are identical.");} else { console.log("Given trees are not identical.");}// This code is contributed by adityamaharshi |
Output
Both the trees are identical.
Time complexity: O(N)
Auxiliary Space: O(N), since using auxiliary ArrayList and call stack
The Way We Can Determine Trees are Identical Only Using Pre-Order Traversal:
The Approach:
Here in this Approach we are storing preorder traversal of tree where we store zero(0)(we can store any another number so that we donot miss any node such as INT_MAX or -10000) for the null node and then we compare both vector if they are same then return true both the trees are identical.
C++
/* CPP code to check if two trees are identical */#include <bits/stdc++.h>using namespace std;/* A binary tree node */class Node {public: int data; Node* left; Node* right; Node(int d) { this->data = d; this->left = NULL; this->right = NULL; }};void preorder(Node* root,vector<int>&v){ if(root==NULL){ // v.push_back(0); return; } v.push_back(root->data); if(root->left)preorder(root->left,v); if(!root->left)v.push_back(0); if(root->right)preorder(root->right,v); if(!root->right)v.push_back(0); }bool isIdentical(Node* root1,Node*root2){ vector<int>v,x; preorder(root1,v); preorder(root2,x); // for(auto it:v)cout<<it<<" "; // cout<<endl; return v==x;}int main() { Node* root1 = new Node(1); root1->left = new Node(2); root1->right = new Node(3); root1->left->left = new Node(4); root1->left->right = new Node(5); Node* root2 = new Node(1); root2->left = new Node(2); root2->right = new Node(3); root2->left->left = new Node(4); root2->left->right = new Node(5); // Function call if (isIdentical(root1, root2)) { cout << "Both the trees are identical." << endl; } else { cout << "Given trees are not identical." << endl; }} |
Java
// Java code for the above approachimport java.util.Vector;/* A binary tree node */class Node { int data; Node left; Node right; Node(int d) { this.data = d; this.left = null; this.right = null; }}public class Main { /* Function to traverse the tree in pre-order */ public void preorder(Node root, Vector<Integer> v) { if (root == null) { // v.add(0); return; } v.add(root.data); if (root.left != null) { preorder(root.left, v); } else { v.add(0); } if (root.right != null) { preorder(root.right, v); } else { v.add(0); } } /* Function to check if two trees are identical */ public boolean isIdentical(Node root1, Node root2) { Vector<Integer> v = new Vector<Integer>(); Vector<Integer> x = new Vector<Integer>(); preorder(root1, v); preorder(root2, x); // for (Integer it : v) { // System.out.print(it + " "); // } // System.out.println(); return v.equals(x); } public static void main(String[] args) { Node root1 = new Node(1); root1.left = new Node(2); root1.right = new Node(3); root1.left.left = new Node(4); root1.left.right = new Node(5); Node root2 = new Node(1); root2.left = new Node(2); root2.right = new Node(3); root2.left.left = new Node(4); root2.left.right = new Node(5); Main main = new Main(); // Function call if (main.isIdentical(root1, root2)) { System.out.println("Both the trees are identical."); } else { System.out.println("Given trees are not identical."); } }}// This code is contributed by lokeshpotta20. |
Python3
class Node: def __init__(self, d): self.data = d self.left = None self.right = Nonedef preorder(root, v): if root == None: return v.append(root.data) if root.left: preorder(root.left, v) else: v.append(0) if root.right: preorder(root.right, v) else: v.append(0)def isIdentical(root1, root2): v = [] x = [] preorder(root1, v) preorder(root2, x) return v == xroot1 = Node(1)root1.left = Node(2)root1.right = Node(3)root1.left.left = Node(4)root1.left.right = Node(5)root2 = Node(1)root2.left = Node(2)root2.right = Node(3)root2.left.left = Node(4)root2.left.right = Node(5)if isIdentical(root1, root2): print("Both the trees are identical.")else: print("Given trees are not identical.") |
C#
// C# program to see if two trees are identicalusing System;using System.Linq;using System.Collections.Generic;// A binary tree nodepublic class Node{ public int data; public Node left, right; public Node(int item){ data = item; left = right = null; }} public class BinaryTree { public Node root1, root2; public void preorder(Node root, List<int> v){ if(root == null) return; v.Add(root.data); if(root.left != null) preorder(root.left, v); if(root.left == null) v.Add(0); if(root.right != null) preorder(root.right, v); if(root.right == null) v.Add(0); } public bool isIdentical(Node root1, Node root2){ List<int> v = new List<int>(); List<int> x = new List<int>(); preorder(root1, v); preorder(root2, x); return Enumerable.SequenceEqual(v, x); } public static void Main(string[] args){ BinaryTree tree = new BinaryTree(); tree.root1 = new Node(1); tree.root1.left = new Node(2); tree.root1.right = new Node(3); tree.root1.left.left = new Node(4); tree.root1.left.right = new Node(5); tree.root2 = new Node(1); tree.root2.left = new Node(2); tree.root2.right = new Node(3); tree.root2.left.left = new Node(4); tree.root2.left.right = new Node(5); // Function call if (tree.isIdentical(tree.root1, tree.root2)) { Console.WriteLine("Both the trees are identical."); } else { Console.WriteLine("Given trees are not identical."); } }} // THIS CODE IS CONTRIBUTED BY KIRTI AGARWAL(KIRTIAGARWAL23121999) |
Javascript
/* Javascript code to check if two trees are identical *//* A binary tree node */class Node { constructor(d) { this.data = d; this.left = null; this.right = null; }}function preorder( root, v){ if(root==null){ // v.push_back(0); return; } v.push(root.data); if(root.left) preorder(root.left,v); if(!root.left) v.push(0); if(root.right) preorder(root.right,v); if(!root.right) v.push(0); }function isIdentical( root1,root2){ let v=[]; let x=[]; preorder(root1,v); preorder(root2,x); if(v.length!=x.length) return 0; for(let i=0; i<v.length; i++) if(x[i]!=v[i]) return 0; return 1;}let root1 = new Node(1);root1.left = new Node(2);root1.right = new Node(3);root1.left.left = new Node(4);root1.left.right = new Node(5);let root2 = new Node(1);root2.left = new Node(2);root2.right = new Node(3);root2.left.left = new Node(4);root2.left.right = new Node(5);// Function callif (isIdentical(root1, root2)) { console.log("Both the trees are identical.\n");}else { console.log("Given trees are not identical.\n");} |
Output
Both the trees are identical.
Time complexity: O(N)+O(M)
Auxiliary Space: O(N)+O(M) for vectors.
Using the Level Order traversal:
The idea behind this approach to solve the above problem is to traverse both trees level by level and compare the values of the nodes at each level. We can use a queue to store the nodes of both trees in a level order manner.
Follow the below steps to implement the above idea:
- Enqueue the root nodes of both trees into a queue.
- While the queue is not empty, dequeue the front nodes of both trees and compare their values.
- If the values are not equal, return false.
- If the values are equal, enqueue the left and right child nodes of both trees, if they exist, into the queue.
- Repeat steps 2-4 until either the queue becomes empty or we find two nodes with unequal values.
- If the queue becomes empty and we have not found any nodes with unequal values, return true indicating that the trees are identical.
Below is the implementation of the above approach:
C++
// C++ code to implement the Level order traversal approach#include <iostream>#include <queue>using namespace std;// Definition of a Binary Tree Nodestruct Node { int data; Node* left; Node* right; Node(int val) { data = val; left = NULL; right = NULL; }};// Function to check if two trees are identical or notbool isIdentical(Node* root1, Node* root2){ // Base case: if both roots are NULL, then trees are // identical if (root1 == NULL && root2 == NULL) return true; // If one of the roots is NULL, then trees are not // identical if (root1 == NULL || root2 == NULL) return false; // Create queues to perform level order traversal on // both trees queue<Node*> q1, q2; // Add the roots of both trees to their respective // queues q1.push(root1); q2.push(root2); // Loop until either of the queues becomes empty while (!q1.empty() && !q2.empty()) { // Get the front node from both queues Node* curr1 = q1.front(); q1.pop(); Node* curr2 = q2.front(); q2.pop(); // If the data of the current nodes is not equal, // then trees are not identical if (curr1->data != curr2->data) return false; // If the left child of one tree exists and the left // child of the other tree does not exist, then // trees are not identical if (curr1->left != NULL && curr2->left == NULL) return false; if (curr1->left == NULL && curr2->left != NULL) return false; // If the right child of one tree exists and the // right child of the other tree does not exist, // then trees are not identical if (curr1->right != NULL && curr2->right == NULL) return false; if (curr1->right == NULL && curr2->right != NULL) return false; // If both left and right children of both trees // exist, then add them to their respective queues if (curr1->left != NULL && curr2->left != NULL) { q1.push(curr1->left); q2.push(curr2->left); } if (curr1->right != NULL && curr2->right != NULL) { q1.push(curr1->right); q2.push(curr2->right); } } // If we have reached this point, then trees are // identical return true;}// Driver Codeint main(){ // Create the first tree Node* root1 = new Node(1); root1->left = new Node(2); root1->right = new Node(3); root1->left->left = new Node(4); root1->left->right = new Node(5); // Create the second tree Node* root2 = new Node(1); root2->left = new Node(2); root2->right = new Node(3); root2->left->left = new Node(4); root2->left->right = new Node(5); // Check if the trees are identical or not if (isIdentical(root1, root2)) cout << "The trees are identical" << endl; else cout << "The trees are not identical" << endl; return 0;}// This code is contributed by Veerendra_Singh_Rajpoot |
Java
/*package whatever //do not write package name here */import java.util.LinkedList;import java.util.Queue;class Node { int data; Node left; Node right; Node(int val) { data = val; left = null; right = null; }}public class IdenticalTrees { public static boolean isIdentical(Node root1, Node root2) { if (root1 == null && root2 == null) { // Base case: if both roots are null, then trees // are identical return true; } if (root1 == null || root2 == null) { // If one of the roots is null, then trees are // not identical return false; } Queue<Node> q1 = new LinkedList<Node>(); Queue<Node> q2 = new LinkedList<Node>(); q1.add(root1); q2.add(root2); while (!q1.isEmpty() && !q2.isEmpty()) { Node curr1 = q1.poll(); Node curr2 = q2.poll(); if (curr1.data != curr2.data) { // If the data of the current nodes is not // equal, then trees are not identical return false; } if (curr1.left != null && curr2.left == null || curr1.left == null && curr2.left != null) { // If the left child of one tree exists and // the left child of the other tree does not // exist, then trees are not identical return false; } if (curr1.right != null && curr2.right == null || curr1.right == null && curr2.right != null) { // If the right child of one tree exists and // the right child of the other tree does // not exist, then trees are not identical return false; } if (curr1.left != null && curr2.left != null) { q1.add(curr1.left); q2.add(curr2.left); } if (curr1.right != null && curr2.right != null) { q1.add(curr1.right); q2.add(curr2.right); } } // If we have reached this point, then trees are // identical return true; } public static void main(String[] args) { // Create the first tree Node root1 = new Node(1); root1.left = new Node(2); root1.right = new Node(3); root1.left.left = new Node(4); root1.left.right = new Node(5); // Create the second tree Node root2 = new Node(1); root2.left = new Node(2); root2.right = new Node(3); root2.left.left = new Node(4); root2.left.right = new Node(5); // Check if the trees are identical or not if (isIdentical(root1, root2)) { System.out.println("The trees are identical"); } else { System.out.println( "The trees are not identical"); } }} |
Python3
# Python code to implement the Level order traversal approachfrom queue import Queue# Definition of a Binary Tree Nodeclass Node: def __init__(self, val): self.data = val self.left = None self.right = None# Function to check if two trees are identical or notdef isIdentical(root1, root2): # Base case: if both roots are None, then trees are # identical if not root1 and not root2: return True # If one of the roots is None, then trees are not # identical if not root1 or not root2: return False # Create queues to perform level order traversal on # both trees q1 = Queue() q2 = Queue() # Add the roots of both trees to their respective # queues q1.put(root1) q2.put(root2) # Loop until either of the queues becomes empty while not q1.empty() and not q2.empty(): # Get the front node from both queues curr1 = q1.get() curr2 = q2.get() # If the data of the current nodes is not equal, # then trees are not identical if curr1.data != curr2.data: return False # If the left child of one tree exists and the left # child of the other tree does not exist, then # trees are not identical if (curr1.left and not curr2.left) or (not curr1.left and curr2.left): return False # If the right child of one tree exists and the # right child of the other tree does not exist, # then trees are not identical if (curr1.right and not curr2.right) or (not curr1.right and curr2.right): return False # If both left and right children of both trees # exist, then add them to their respective queues if curr1.left and curr2.left: q1.put(curr1.left) q2.put(curr2.left) if curr1.right and curr2.right: q1.put(curr1.right) q2.put(curr2.right) # If we have reached this point, then trees are # identical return True# Driver Codeif __name__ == '__main__': # Create the first tree root1 = Node(1) root1.left = Node(2) root1.right = Node(3) root1.left.left = Node(4) root1.left.right = Node(5) # Create the second tree root2 = Node(1) root2.left = Node(2) root2.right = Node(3) root2.left.left = Node(4) root2.left.right = Node(5) # Check if the trees are identical or not if isIdentical(root1, root2): print("The trees are identical") else: print("The trees are not identical")#This code is contributed by shivamsharma215 |
C#
using System;using System.Collections.Generic;// Definition of a Binary Tree Nodepublic class Node { public int data; public Node left; public Node right; public Node(int val) { data = val; left = null; right = null; }};public class Gfg { // Function to check if two trees are identical or not public static bool isIdentical(Node root1, Node root2) { // Base case: if both roots are null, then trees are // identical if (root1 == null && root2 == null) return true; // If one of the roots is null, then trees are not // identical if (root1 == null || root2 == null) return false; // Create queues to perform level order traversal on // both trees Queue<Node> q1 = new Queue<Node>(); Queue<Node> q2 = new Queue<Node>(); // Add the roots of both trees to their respective // queues q1.Enqueue(root1); q2.Enqueue(root2); // Loop until either of the queues becomes empty while (q1.Count != 0 && q2.Count != 0) { // Get the front node from both queues Node curr1 = q1.Dequeue(); Node curr2 = q2.Dequeue(); // If the data of the current nodes is not equal, // then trees are not identical if (curr1.data != curr2.data) return false; // If the left child of one tree exists and the left // child of the other tree does not exist, then // trees are not identical if (curr1.left != null && curr2.left == null) return false; if (curr1.left == null && curr2.left != null) return false; // If the right child of one tree exists and the // right child of the other tree does not exist, // then trees are not identical if (curr1.right != null && curr2.right == null) return false; if (curr1.right == null && curr2.right != null) return false; // If both left and right children of both trees // exist, then add them to their respective queues if (curr1.left != null && curr2.left != null) { q1.Enqueue(curr1.left); q2.Enqueue(curr2.left); } if (curr1.right != null && curr2.right != null) { q1.Enqueue(curr1.right); q2.Enqueue(curr2.right); } } // If we have reached this point, then trees are // identical return true; } // Driver Code static void Main() { // Create the first tree Node root1 = new Node(1); root1.left = new Node(2); root1.right = new Node(3); root1.left.left = new Node(4); root1.left.right = new Node(5); // Create the second tree Node root2 = new Node(1); root2.left = new Node(2); root2.right = new Node(3); root2.left.left = new Node(4); root2.left.right = new Node(5); // Check if the trees are identical or not if (isIdentical(root1, root2)) Console.WriteLine("The trees are identical"); else Console.WriteLine("The trees are not identical"); }} |
Javascript
// JavaScript code to implement the Level order traversal approach// Definition of a Binary Tree Nodeclass Node { constructor(val) { this.data = val; this.left = null; this.right = null; }}// Function to check if two trees are identical or notfunction isIdentical(root1, root2) { // Base case: if both roots are null, then trees are identical if (!root1 && !root2) return true; // If one of the roots is null, then trees are not identical if (!root1 || !root2) return false; // Create queues to perform level order traversal on both trees const q1 = [], q2 = []; // Add the roots of both trees to their respective queues q1.push(root1); q2.push(root2); // Loop until either of the queues becomes empty while (q1.length && q2.length) { // Get the front node from both queues const curr1 = q1.shift(); const curr2 = q2.shift(); // If the data of the current nodes is not equal, then trees are not identical if (curr1.data !== curr2.data) return false; // If the left child of one tree exists and the left child of the other tree does not exist, then trees are not identical if (curr1.left && !curr2.left) return false; if (!curr1.left && curr2.left) return false; // If the right child of one tree exists and the right child of the other tree does not exist, then trees are not identical if (curr1.right && !curr2.right) return false; if (!curr1.right && curr2.right) return false; // If both left and right children of both trees exist, then add them to their respective queues if (curr1.left && curr2.left) { q1.push(curr1.left); q2.push(curr2.left); } if (curr1.right && curr2.right) { q1.push(curr1.right); q2.push(curr2.right); } } // If we have reached this point, then trees are identical return true;}// Driver Code// Create the first treeconst root1 = new Node(1);root1.left = new Node(2);root1.right = new Node(3);root1.left.left = new Node(4);root1.left.right = new Node(5);// Create the second treeconst root2 = new Node(1);root2.left = new Node(2);root2.right = new Node(3);root2.left.left = new Node(4);root2.left.right = new Node(5);// Check if the trees are identical or notif (isIdentical(root1, root2)) console.log("The trees are identical");else console.log("The trees are not identical"); |
Output
The trees are identical
Time complexity: O(N) , the time complexity will be proportional to the total number of nodes.
Auxiliary Space: O(N), The auxiliary space complexity of the level order traversal approach is O(n), where n is the total number of nodes in both trees.
Using the 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++
// C++ code to implement the Morris traversal approach#include <iostream>using namespace std;/* A binary tree node */struct Node { int data; Node *left, *right; Node(int x) { data = x; left = right = NULL; }};/* Morris traversal approach to check if two binary trees * are identical */bool isIdentical(Node* r1, Node* r2){ // Base cases if (r1 == NULL && r2 == NULL) // both trees are empty return true; if (r1 == NULL || r2 == NULL) // one of the trees is empty, which // means they are not identical return false; // Morris traversal while (r1 != NULL && r2 != NULL) { if (r1->data != r2->data) // if the data of the current nodes // is not the same, then the trees // are not identical return false; // Morris traversal for r1 if (r1->left == NULL) { // if the left child is NULL, move to // the right child r1 = r1->right; } else { // if the left child is not NULL, find the // predecessor Node* pre = r1->left; while (pre->right != NULL && pre->right != r1) // find the rightmost node // in the left subtree 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; } } } return (r1 == NULL && r2 == NULL); // if both r1 and r2 are NULL, // then the trees are identical}/* Driver code */int main(){ // Construct the first tree Node* root1 = new Node(1); root1->left = new Node(2); root1->right = new Node(3); root1->left->left = new Node(4); root1->left->right = new Node(5); // Construct the second tree Node* root2 = new Node(1); root2->left = new Node(2); root2->right = new Node(3); root2->left->left = new Node(4); root2->left->right = new Node(5); // Check if the trees are identical if (isIdentical(root1, root2)) cout << "Both trees are identical"; else cout << "Both trees are not identical"; return 0;}// This code is contributed by Veerendra_Singh_Rajpoot |
Java
// Java code to implement the Morris traversal approachclass Node { int data; Node left, right; Node(int item) { data = item; left = right = null; }}public class IdenticalBinaryTrees { // Morris traversal approach to check if two binary trees // are identical public static boolean isIdentical(Node r1, Node r2) { // Base cases if (r1 == null && r2 == null) // both trees are empty return true; if (r1 == null || r2 == null) // one of the trees is empty, which // means they are not identical return false; // Morris traversal while (r1 != null && r2 != null) { if (r1.data != r2.data) // if the data of the current nodes // is not the same, then the trees // are not identical return false; // Morris traversal for r1 if (r1.left == null) { // if the left child is NULL, move to // the right child r1 = r1.right; } else { // if the left child is not NULL, find the // predecessor Node pre = r1.left; while (pre.right != null && pre.right != r1) // find the rightmost node // in the left subtree 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; } } } return (r1 == null && r2 == null); // if both r1 and r2 are NULL, // then the trees are identical } // Driver code public static void main(String[] args) { // Construct the first tree Node root1 = new Node(1); root1.left = new Node(2); root1.right = new Node(3); root1.left.left = new Node(4); root1.left.right = new Node(5); // Construct the second tree Node root2 = new Node(1); root2.left = new Node(2); root2.right = new Node(3); root2.left.left = new Node(4); root2.left.right = new Node(5); // Check if the trees are identical if (isIdentical(root1, root2)) System.out.println("Both trees are identical"); else System.out.println("Both trees are not identical"); }}//This code is contributed by Veerendra_Singh_Rajpoot |
Python3
# A binary tree nodeclass Node: def __init__(self, x): self.data = x self.left = None self.right = None# Morris traversal approach to check if two binary trees are identicaldef isIdentical(r1, r2): # Base cases if not r1 and not r2: # both trees are empty return True if not r1 or not r2: # one of the trees is empty, which means they are not identical return False # Morris traversal while r1 and r2: if r1.data != r2.data: # if the data of the current nodes is not the same, then the trees are not identical return False # Morris traversal for r1 if not r1.left: # if the left child is None, move to the right child r1 = r1.right else: # if the left child is not None, find the predecessor pre = r1.left while pre.right and pre.right != r1: # find the rightmost node in the left subtree 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 = r1 r1 = r1.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 r1 = r1.right # Morris traversal for r2, same as for r1 if not r2.left: r2 = r2.right else: pre = r2.left while pre.right and pre.right != r2: pre = pre.right if not pre.right: pre.right = r2 r2 = r2.left else: pre.right = None r2 = r2.right return not r1 and not r2 # if both r1 and r2 are None, then the trees are identical# Driver codeif __name__ == "__main__": # Construct the first tree root1 = Node(1) root1.left = Node(2) root1.right = Node(3) root1.left.left = Node(4) root1.left.right = Node(5) # Construct the second tree root2 = Node(1) root2.left = Node(2) root2.right = Node(3) root2.left.left = Node(4) root2.left.right = Node(5) # Check if the trees are identical if isIdentical(root1, root2): print("Both trees are identical") else: print("Both trees are not identical")# This code is contributed by rambabuguphka |
C#
using System;public class Node{ public int data; public Node left, right; public Node(int x) { data = x; left = right = null; }}public class IdenticalTrees{ // Morris traversal approach to check if two binary trees // * are identical public static bool IsIdentical(Node r1, Node r2) { // Base cases if (r1 == null && r2 == null) // both trees are empty return true; if (r1 == null || r2 == null) // one of the trees is empty return false; while (r1 != null && r2 != null) { if (r1.data != r2.data) // if the data of the current nodes is not the same return false; // Morris traversal for r1 if (r1.left == null) { r1 = r1.right; } else { Node pre = r1.left; while (pre.right != null && pre.right != r1) pre = pre.right; if (pre.right == null) { pre.right = r1; r1 = r1.left; } else { 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; } } } return r1 == null && r2 == null; // if both r1 and r2 are null, // then the trees are identical } public static void Main(string[] args) { Node root1 = new Node(1); root1.left = new Node(2); root1.right = new Node(3); root1.left.left = new Node(4); root1.left.right = new Node(5); Node root2 = new Node(1); root2.left = new Node(2); root2.right = new Node(3); root2.left.left = new Node(4); root2.left.right = new Node(5); if (IsIdentical(root1, root2)) Console.WriteLine("Both trees are identical"); else Console.WriteLine("Both trees are not identical"); }}// This code is contributed by rambabuguphka |
Javascript
// Javascript code to implement the Morris traversal approachclass Node { constructor(item) { this.data = item; this.left = null; this.right = null; }}// Morris traversal approach to check if two binary trees are identicalfunction isIdentical(r1, r2) { if (r1 === null && r2 === null) { return true; } if (r1 === null || r2 === null) { return false; } // Morris traversal while (r1 !== null && r2 !== null) { if (r1.data !== r2.data) { return false; } // Morris traversal for r1 if (r1.left === null) { r1 = r1.right; } else { let pre = r1.left; while (pre.right !== null && pre.right !== r1) { pre = pre.right; } if (pre.right === null) { pre.right = r1; r1 = r1.left; } else { pre.right = null; r1 = r1.right; } } // Morris traversal for r2 if (r2.left === null) { r2 = r2.right; } else { let 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; } } } return r1 === null && r2 === null; // if both r1 and r2 are NULL // then the trees are identical}// Construct the first treeconst root1 = new Node(1);root1.left = new Node(2);root1.right = new Node(3);root1.left.left = new Node(4);root1.left.right = new Node(5);// Construct the second treeconst root2 = new Node(1);root2.left = new Node(2);root2.right = new Node(3);root2.left.left = new Node(4);root2.left.right = new Node(5);// Check if the trees are identicalif (isIdentical(root1, root2)) { console.log("Both trees are identical");} else { console.log("Both trees are not identical");}// This code is contributed by guptapratik |
Output
Both trees are identical
Time Complexity: O(N) ,The time complexity of the Morris traversal approach for checking if two binary trees are identical is O(n), where n is the total number of nodes in the trees. This is because each node is visited only once, and the traversal does not involve any recursion or extra data structures.
Auxiliary Space: O(1) , The space complexity of the Morris traversal approach is O(1), which means that the space required by the algorithm is constant and does not depend on the size of the input. This is because the traversal only requires a few pointers to the tree nodes and does not use any additional data structures, such as stacks or queues, to store intermediate results.
Related Article: Iterative function to check if two trees are identical.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
