Symmetric Tree (Mirror image of itself)

You are given a binary tree, check whether it is symmetric or not. A symmetric tree is one if it is a mirror image of itself.

For example. Consider the binary tree below.

     1
   /   \
  2     2
 / \   / \
3   4 4   3

The binary tree shown above is symmetric since it is the mirror image of itself.
    1
   / \
  2   2
   \   \
   3    3

But the tree above is not symmetric.

Algorithm

  1. We create a recursive function which takes as argument the roots of two trees and recursively checks whether the two trees and its subtrees are mirror of itself or not.
  2. If both the roots are null pointers, we return True. If any one of them is null pointer, we return false. If both has the same value and the recursive call on root1’s left child and root2’s right child and also the recursive call on root1’s right child and root2’s left child, returns True, then we can say that the Tree is symmetric else it’s not.
#include <bits/stdc++.h>

using namespace std;

struct Node{
  Node* left;
  Node* right;
  int data;
};

Node* createNode(int key){
    Node* temp = new Node();
    temp->data = key;
    temp->right = nullptr;
    temp->left = nullptr;
    return temp;
}

Node* root = nullptr;

Node* insertNode(Node* node, int key){
    Node* temp = createNode(key);
    if(root == nullptr){
        root = temp;
        return root;
    }
    if(node == nullptr){
        return temp;   
    }
    
    if(key < node->data){
        node->left = insertNode(node->left, key);
    }else if(key > node->data){
        node->right = insertNode(node->right, key);
    }
    return node;
}

bool func(Node* root1, Node* root2){
    if(root1 == nullptr && root2==nullptr){
        return true;
    }
    if(root1==nullptr || root2==nullptr){
        return false;
    }
    return (root1->data == root2->data) && func(root1->left, root2->right) && func(root1->right, root2->left);
}
bool isSymmetric(Node* root) {
    return func(root, root);
}


void levelOrderTraversal(){
    Node* temp = root;
    queue<Node*> q;
    q.push(temp);
    while(!q.empty()){
        Node* front = q.front();
        cout<<front->data<<" ";
        q.pop();
        if(front->left != nullptr){
            q.push(front->left);
        }
        if(front->right != nullptr){
            q.push(front->right);
        }
    }
}

int main()
{
    insertNode(root, 8);
    insertNode(root, 3);
    insertNode(root, 10);
    insertNode(root, 1);
    insertNode(root, 6);
    insertNode(root, 14);
    insertNode(root, 4);
    insertNode(root, 7);
    insertNode(root, 13);
    levelOrderTraversal();
    cout<<endl;
    if(isSymmetric(root)){
        cout<<"The tree is symmetric";
    }else{
        cout<<"The tree is not symmetric";
    }
    return 0;
}

Also, check out another popular interview problem K’th smallest element in an unordered list.

One comment

Leave a Reply

Your email address will not be published.