Check whether two trees are symmetrical or not
Check for symmetrical trees
In this article, we will learn the approach and code about how check whether two trees are symmetrical in C++. Two binary trees are said to be symmetrical if both the trees are mirror images of each other.
Check Whether Two Trees are Symmetrical or Not
Algorithm :
- Create a recursive function isMirror() that takes two trees as an argument and returns 1 if trees are the mirrored and 0 if trees are not mirrored.
- The isSMirror() function recursively checks two roots and subtrees under the root.
- And isSymmetric() takes the root of the binary tree as an parameter and then will return true is isMirror() returns 1, otherwise it return 1.
- If isSymmetric() returns 1 it means that given tree is symmetric, otherwise not symmetric.
Code Implementation to check whether two trees are symmetrical or not in C++
Run
#include<bits/stdc++.h>
using namespace std;
struct Node
{
int val;
Node *left;
Node *right;
Node (int x):val (x), left (NULL), right (NULL)
{
}
};
bool isSymmetric (Node * root1, Node * root2)
{
if (root1 == NULL && root2 == NULL)
{
return true;
}
else if (root1 == NULL || root2 == NULL)
{
return false;
}
else
{
return (root1->val == root2->val) && isSymmetric (root1->left, root2->right) && isSymmetric (root1->right, root2->left);
}
}
bool isSymmetricTree (Node * root)
{
if (root == NULL)
{
return true;
}
else
{
return isSymmetric (root->left, root->right);
}
}
int main ()
{
// Construct two sample binary trees.
Node *root1 = new Node (1);
root1->left = new Node (2);
root1->right = new Node (2);
root1->left->left = new Node (3);
root1->left->right = new Node (4);
root1->right->left = new Node (4);
root1->right->right = new Node (3);
Node *root2 = new Node (1);
root2->left = new Node (2);
root2->right = new Node (2);
root2->left->left = new Node (3);
root2->left->right = new Node (4);
root2->right->left = new Node (4);
root2->right->right = new Node (5);
// Check whether the two binary trees are symmetrical or not.
bool isSymmetric1 = isSymmetricTree (root1);
bool isSymmetric2 = isSymmetricTree (root2);
if (isSymmetric1)
{
cout << "The first binary tree is symmetrical." << endl;
}
else
{
cout << "The first binary tree is not symmetrical." << endl;
}
if (isSymmetric2)
{
cout << "The second binary tree is symmetrical." << endl;
}
else
{
cout << "The second binary tree is not symmetrical." << endl;
}
return 0;
}
Output: The first binary tree is symmetrical. The second binary tree is not symmetrical.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
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
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
Login/Signup to comment