Check whether 2 Binary trees are identical or not
Check for identical binary trees
A binary tree is said to be identical with another binary tree if both the trees have the same data and also the same arrangement of the data.In this article, we will learn the approach and code to check whether 2 binary trees are identical or not.
What are identical Trees?
Given root nodes of 2 trees and we need to find that whether the trees are identical or not.
Trees being identical means that they are same in terms of structures, same in terms of the number of nodes and also same in terms of links.
Eg:- (Insert Image)
For the above Input, the value returned by the method for trees 1 and 2 should be true as both the trees are identical.
Trees 1 and 2 are identical to each other whereas 2 and 3 are not.
Approach:-
Inorder to compare two trees we can traverse the trees , store their traversal sequences in an array and then match two arrays .
However, this approach might not always be right. There might be an exception to the case wherever the traversal leads the same result but trees are not identical.
This is left as an exercise to the reader to think of an example where trees have traversal sequence same but aren’t identical.
Code Implementation to check whether two binary trees are identical or not in C++
#include<bits/stdc++.h>
struct node
{
int val;
struct node *lchild;
struct node *rchild;
};
struct node *newNode (int key)
{
struct node *newnode = (struct node *) malloc (sizeof (struct node));
newnode->val = key;
newnode->lchild = NULL;
newnode->rchild = NULL;
return (newnode);
}
int areidentical (struct node *node1, struct node *node2)
{
if (node1 == NULL && node2 == NULL)
return 1;
if (node1 != NULL && node2 != NULL)
{
return (node1->val == node2->val
&& areidentical (node1->lchild, node2->lchild)
&& areidentical (node1->rchild, node2->rchild));
}
else
return 0;
}
int main ()
{
struct node *root1 = newNode (232);
struct node *root2 = newNode (232);
root1->lchild = newNode (231);
root1->rchild = newNode (231);
root1->lchild->lchild = newNode (431);
root1->lchild->rchild = newNode (531);
root2->lchild = newNode (231);
root2->rchild = newNode (331);
root2->lchild->lchild = newNode (431);
root2->lchild->rchild = newNode (513);
if (areidentical (root1, root2))
printf ("Both tree are identical.");
else
printf ("Trees are not identical.");
getchar ();
return 0;
}
Output: Trees are not identical.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Introduction to Trees
Binary Trees
- Binary Tree in Data Structures (Introduction)
- Tree Traversals: Inorder Postorder Preorder : C | C++ | Java
- Inorder Postorder PreOrder Traversals Examples
- Tree Traversal without Recursion
Binary Search Trees
Traversals
- Traversal in Trees
- Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
- Tree Traversals: Depth First Search (DFS) : C | C++ | Java
- Construct a Binary Tree from Postorder and Inorder
B – Trees
AVL Trees
- AVL Trees
Complete Programs for Trees
- Depth First Traversals – C | C++ | Java
- Level Order Traversal – C | C++ | Java
- Construct Tree from given Inorder and Preorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Inorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Preorder traversal – C | C++ | Java
- Find size of the Binary tree – C | C++ | Java
- Find the height of binary tree – C | C++ | Java
- Find maximum in binary tree – C | C++ | Java
- Check whether two tree are identical- C| C++| Java
- Spiral Order traversal of Tree- C | C++| Java
- Level Order Traversal Line by Line – C | C++| Java
- Hand shaking lemma and some Impotant Tree Properties.
- Check If binary tree if Foldable or not.- C| C++| Java
- check whether tree is Symmetric – C| C++| Java.
- Check for Children-Sum in Binary Tree- C|C++| Java
- Sum of all nodes in Binary Tree- C | C++ | Java
- Lowest Common Ancestor in Binary Tree- C | C++ | Java
Introduction to Trees
Binary Trees
- Binary Tree in Data Structures (Introduction)
- Tree Traversals: Inorder Postorder Preorder : C | C++ | Java
- Inorder Postorder PreOrder Traversals Examples
- Tree Traversal without Recursion
Binary Search Trees
Traversals
- Traversal in Trees
- Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
- Tree Traversals: Depth First Search (DFS) : C | C++ | Java
- Construct a Binary Tree from Postorder and Inorder
B – Trees
AVL Trees
- AVL Trees
Complete Programs for Trees
- Depth First Traversals – C | C++ | Java
- Level Order Traversal – C | C++ | Java
- Construct Tree from given Inorder and Preorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Inorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Preorder traversal – C | C++ | Java
- Find size of the Binary tree – C | C++ | Java
- Find the height of binary tree – C | C++ | Java
- Find maximum in binary tree – C | C++ | Java
- Check whether two tree are identical- C| C++| Java
- Spiral Order traversal of Tree- C | C++| Java
- Level Order Traversal LIne by Line – C | C++| Java
- Hand shaking lemma and some Impotant Tree Properties.
- Check If binary tree if Foldable or not.- C| C++| Java
- check whether tree is Symmetric C| C++| Java.
- Check for Children-Sum in Binary Tree- C|C++| Java
- Sum of all nodes in Binary Tree- C | C++ | Java
- Lowest Common Ancestor in Binary Tree. C | C++ | Java
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment