Foldable Binary Tree in C++
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 If binary tree is Foldable or not in C++
Algorithm :
- If tree is empty, then return true.
- Convert the left subtree to its mirror image mirror(root->left);
- Check if the structure of left subtree and right subtree is same and store the result. res = isStructSame(root->left, root->right);
- isStructSame() recursively compares structures of two subtrees and returns true if structures are same
- Revert the changes made in step 2 to get the original tree. mirror(root->left);
- Return result res stored in step 2.
Code Implementation to check if binary tree is foldable 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 isMirror (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) &&
isMirror (root1->left, root2->right) &&
isMirror (root1->right, root2->left);
}
}
bool isFoldable (Node * root)
{
if (root == NULL)
{
return true;
}
else
{
return isMirror (root->left, root->right);
}
}
int main ()
{
Node *root = new Node (1);
root->left = new Node (2);
root->left->right = new Node (3);
root->right = new Node (4);
root->right->left = new Node (5);
bool isFoldableTree = isFoldable (root);
if (isFoldableTree)
{
cout << "The binary tree is foldable." << endl;
}
else
{
cout << "The binary tree is not foldable." << endl;
}
return 0;
}
Output:
The binary tree is not foldable.
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