Foldable Binary Tree in C++

March 16, 2023

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.

Foldable Binary Tree in C++

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.
Check If binary tree is Foldable or not in C Language
DSA desktop gif
DSA mobile gif

Find the size of binary tree

Find maximum in binary tree

Level Order Traversal LIne by Line

Lowest Common Ancestor in Binary Tree

Check for Children-Sum in Binary Tree

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

Get Prime

Introduction to Trees

Binary Trees

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
    • AVL Trees: Introduction
    • AVL Tree Insertion : C | C++ | Java
    • AVL Tree Deletion : C | C++ | Java
    • Insertion in a Binary Tree (Level Order) – C | C++ | Java
    • Searching in Binary Tree – C | C++ | Java
    • Searching in a Binary Search Tree – C | C++ | Java

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 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
    • AVL Trees: Introduction
    • AVL Tree Insertion :  C | C++ | Java
    • AVL Tree Deletion : C | C++ | Java
    • Insertion in a Binary Tree (Level Order) – C | C++ | Java
    • Searching in Binary Tree – C | C++ | Java
    • Searching in a Binary Search Tree – C | C++ | Java

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

Get Prime
Course List
Course List

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout
Checkout