Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Approach & Intuition 
2.1.
Algorithm
2.2.
Code in C++
3.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
Why would you use a recursive solution over the iterative one? 
4.2.
Is a symmetric tree the same as a mirror tree? 
4.3.
What is an empty binary tree? 
5.
Conclusion
Last Updated: Mar 27, 2024
Easy

Symmetric Binary Tree

Author ANKIT MITTAL
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

A Symmetric binary tree is a type of binary tree in which the left part of the root node is identical to the mirror image of the right part and vice versa. We can understand symmetric binary trees with the help of the following diagram. 
 

 

Here, the tree is a symmetric binary tree. We can understand the following with the help of the above definition. Let us divide the above binary tree into 2 parts and take the mirror image of one of the parts. We have taken the left subtree and made its mirror image. We find that the mirror image of the left subtree is similar to the right subtree. Hence the above tree is a symmetric binary tree. 
 

 

The below figure is not a symmetric binary tree as the mirror image of one of the subtrees is not equal to the other. Here in the below diagram, the mirror image of the left subtree is not equal to the right subtree as they differ in alignment.
 

The question we are going to discuss today in this blog is: Given a binary tree, check whether it is a symmetric binary tree or not.

Recommended: Try the Problem by yourself first before moving on to the solution.

Approach & Intuition 

We can analyze that the left and mirror images of the right half must be the same for the tree to be a symmetric binary tree. It is similar to checking the two trees simultaneously at every level. We can also observe that the trees will never be symmetric binary trees if one of the subtrees is null, and if they exist, their value must be the same. This leads us to the recursive approach, which goes like this - check for the left and right nodes of the root whether they both exist, and if they exist, then their value must be the same. We check recursively for every pair of nodes in the left and right subtree if this condition is true. 

Algorithm

We can solve this problem using a recursive algorithm which will be used to traverse the binary tree. This traversal is similar to depth-first search in the graph algorithm. Let us understand this algorithm with the help of the code below: 

Code in C++

#include<iostream>
 using namespace std; 
 
 struct Node {
     int val;
     Node *left;
     Node *right;
     Node(int x){
      val = x; Node* left = NULL; Node*right = NULL;
     }
  };
  
   
    bool solve(Node*a, Node*b){
       // if both left and right subtree are null then the tree is symmetric 
        if(a == NULL && b == NULL)return true; 
        // if both the tree are not null and there subtree are symmetric as well as the 
        // current values of the nodes are equal then we return true
        if(a && b && a->val == b->val && solve(a->left, b->right) && solve(a->right,  b->left))return true; 
        // in every other case(either one of a or b is null or the values of nodes a and b are unequal)  we will return false as the tree can't be symmetric
        return false; 
    }
    
    bool isSymmetric(Node* root) {
        // checking if root is null then the tree is always symmetric 
        if(root == NULL) return true; 
        // here we have seperated the left and the right subtree 
        return solve(root->left, root->right); 
        
    }
    
int main()
{
   // constructing the tree
    Node* root = new Node(2);
    root->left = new Node(3);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(5);
    root->right->right = new Node(4);
 
    if(isSymmetric(root))
      cout<<"Symmetric";
    else
      cout<<"Not symmetric";
    return 0;
}

 

Output :

Symmetric

 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Complexity Analysis

Time Complexity - O(N) 

Since we are traversing every node once, the time complexity to check the symmetric binary tree is of the order N, where N is the number of nodes present in the tree. 

Space Complexity - O(H) 

The space complexity is O(H), where H is the height of the binary tree considering the stack space used during recursion while checking for symmetric subtrees. In the worst case(skewed binary tree), H can be equal to N, where N is the number of nodes in the tree.

Check out this problem - Mirror A Binary Tree

Frequently Asked Questions

Why would you use a recursive solution over the iterative one? 

In competitive programming, you don’t need to implement the fastest possible solution. You only need the solution to be fast enough to pass. To make the code easy and faster to implement, we can use a recursive approach. 

Is a symmetric tree the same as a mirror tree? 

Yes, the symmetric tree is the same as the mirror tree. Both terms are used for the same problem hand in hand. 

What is an empty binary tree? 

The binary tree with no elements is an empty binary tree. null pointer represents a binary tree with no elements. 

Conclusion

We can always break the problem into smaller problems and think. Likewise, in this question, the only catch here is that we need to break the tree into two sub-trees and check the left subtree and the mirror image of the right subtree, by this It simply means we will check for the right node in place of the left node and vice versa because due to the mirror effect the left and the right nodes will act like each other. We can make any subtree (left or right ) to be the mirror and proceed recursively. In these types of questions, the base case is crucial. Here we have accumulated the false conditions since they are more intuitive. Once we have thought of the incorrect conditions, we can simply return true. 

You can also refer to the courses on our platform to master tree data structure.

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Live masterclass