Check for Symmetric Binary Tree (Iterative Approach) in C++

By Amit Raja Kalidindi

In this tutorial, we are going to learn how to check if a given Binary Tree is a Symmetric Tree in C++ using an Iterative approach. If the left subtree and the right subtree of the root of a Binary tree are mirror images of each other, then the Binary Tree is called a Symmetric Tree.

Example:

Conditions for the tree to be symmetric are:

1. The left child of the left subtree must be equal to the right child of the right subtree.
2. The right child of the left subtree must be equal to the left child of the right subtree.

Iterative Approach to Check for Symmetric Tree

1. Create two queues l and r for storing the nodes of the left subtree and the right subtree respectively.
2. Initially push the root of the left subtree into l and push the root of the right subtree into r.
3. While the queues are not empty, repeat the following steps:
   a) Pop the nodes which are at the front of the queues l, r, and assign them to u and v respectively.
   b) Compare u and v. If the data in the nodes are not equal or if only one among the nodes is null then the tree is not symmetric.
   b) Push the left child followed by the right child of u into the queue l.
   c) Push the right child followed by the left child of v into the queue r.
4. If all the comparisons made in step 3b are equal then the tree is symmetric.

Implementation:

#include <bits/stdc++.h>
using namespace std;
struct Node{
    int data;
    Node* left;
    Node* right;
    Node(int val){
        data = val;
        left = NULL,right = NULL;
    }
};
bool isSymmetric(Node* root){
    if(root == NULL){
        return true;
    }
    queue<Node* > l,r;

    /* Push the roots of the left and
       right subtrees into their repective
       queues */
    l.push(root->left);
    r.push(root->right);
    Node *u, *v;
    while(!l.empty() && !r.empty()){
        u = l.front();
        l.pop();
        v = r.front();
        r.pop();

        /* If only one node is null then
           the tree is not symmetric */
        if(u == NULL || v == NULL) {
            if(u == NULL && v == NULL){
                continue;
            }
            return false;
        }
        
        /* If the data in the nodes are not
           equal then the tree is not 
           symmetric */
        if(u->data != v->data){
            return false;
        }
        l.push(u->left);
        l.push(u->right);
                
        r.push(v->right);
        r.push(v->left);
    }
    return true;    
}
int main(){
    Node* root         = new Node(0);
    root->left         = new Node(1);
    root->right        = new Node(1);
    root->left->left   = new Node(2);
    root->left->right  = new Node(3);
    root->right->left  = new Node(3);
    root->right->right = new Node(2);
    if(isSymmetric(root)){
        cout<<"It is a Symmetric Tree"<<endl;
    }
    else{
        cout<<"It is not a Symmetric Tree"<<endl;
    }
}

Output:

It is a Symmetric Tree