Check if Binary Tree is Symmetric or Not

Check if Binary Tree is Symmetric or Not” is a basic problem based on tree data structure. Here, we are given a binary tree and our task is to write a program to check if given binary tree have symmetric structure or not.

A Binary Tree is having symmetric structure if left subtree and right subtree are mirror image of each other, irrespective of node value.

Check if Binary Tree is Symmetric or Not
Symmetric Tree

We have already discussed to check if two binary trees are mirror tree of each other or not. Here, also, we will use same technique to check symmetry of tree.

A Binary Tree is Symmetric if it holds following conditions:

  1. Both Left subtree and right subtree are empty or non-empty.
  2. Left Subtree is mirror image of right subtree, irrespective of data.
  3. Right Subtree is mirror image of left subtree, irrespective of data.

C++ Program to Check if Binary Tree is Symmetric or Not is as follows:

/* C++ Program to Check if Binary Tree is Symmetric or Not */
#include<bits/stdc++.h>
using namespace std;

typedef struct Node
{
    int data;
    struct Node *left;
    struct Node *right;
    Node(int ele)
    {
        data = ele;
        left = NULL;
        right = NULL;
    }
} Node;

/* Function to Check if Binary Tree is Symmetric or Not */
bool checkSymmetry(Node *root1, Node *root2)
{
    /* Base Case1: If both Subtrees are Empty */
    if(root1 == NULL && root2 == NULL)
    return true;
    
    /* Base Case2: If one subtree is empty and other not */
    if(root1 == NULL || root2 == NULL)
    return false;
    
    /*
        If Both are Non-Empty, Recursively compare left subtree 
         with right subtree and vice-versa
    */
    return (root1 != NULL && root2 != NULL) &&
           checkSymmetry(root1 -> left, root2 -> right) &&
           checkSymmetry(root1 -> right,root2 -> left);
}

int main()
{
    /* Creating a Binary trees and inserting some nodes in it */
    Node *root = NULL;
    
    root = new Node(1);
    root -> left = new Node(2);
    root -> right = new Node(3);
    root -> left -> left = new Node(4);
    root -> left -> right = new Node(5);
    root -> right -> left = new Node(6);
    root -> right -> right = new Node (7);
    root -> left -> right -> left = new Node(8);
    root -> right -> left -> right = new Node(9);
    
    /* Calling function to Check if Binary Tree is Symmetric or Not */
    if(checkSymmetry(root -> left, root -> right) == true)
    {
        cout<<"Given Binary Tree is Symmetric Tree!!";
    }
    else
    {
        cout<<"Given Binary Tree is not Symmetric Tree!!";
    }
}

OUTPUT:

Given Binary Tree is Symmetric Tree!!

Related Posts:

  1. Check if two trees are mirror Trees of Each Other
  2. Convert Binary Tree to its Mirror Tree
  3. Introduction to Tree Data Structure
  4. Binary Tree Traversals
  5. Print All Leaf Nodes of a Binary Tree
  6. Count Number of Nodes in a Binary Tree
  7. Print Alternate Levels of Binary Tree
  8. Maximum Width of Binary Tree
  9. Level Order Tree Traversal
  10. Left View of Binary Tree
  11. Right View of Binary Tree
  12. Compute Height of Binary Tree
  13. Inorder Tree Traversal Using Stack
  14. Preorder Tree Trasversal Using Stack
  15. Postorder Tree Traversal Using Stack
  16. Vertical Order Tree Traversal
  17. Top View of Binary Tree
  18. Bottom View of Binary Tree
  19. Delete Complete Binary Tree
  20. Print All Root to Leaf Paths in a Binary Tree

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *