Symmetric Tree

Difficulty Level Easy
Frequently asked in Adobe Amazon Apple Capital One eBay Facebook Fanatics Google MAQ Oracle
Breadth First Search Depth First Search TreeViews 2354

In Symmetric Tree problem we have given a binary tree, check whether it is a mirror of itself. A tree is said to be a mirror image of itself if there exists an axis of symmetry through a root node that divides the tree into two same halves.

Example

Symmetric Tree

Symmetric Tree

Symmetric Tree

Symmetric Tree

Symmetric Tree

Types of Solution for Symmetric Tree

  1. Recursive
  2. Iterative

Recursive

Approach

We use 2 copies of the binary tree say, b1 and b2(to handle left and right subtree separately) and check if :

  1. root value of b1 and b2 are the same or not.
  2. left subtree of b1 and right subtree of b2 are the same(in terms structure as well as node values) or not.
  3. right subtree of b1 and left subtree of b2 is the same(in terms structure as well as node values) or not.

if conditions 1,2 and 3 are true recursively for left and right subtrees we simply return true (else return false).

b1 and b2 have root1 and root2 as root node respectively.

Algorithm for Symmetric Tree

  1. Create two copies of the binary tree (root1 and root2) to handle the left and right subtree separately.
  2. Define the base case.
  3. Check if conditions mentioned above (1,2 and 3) are true or not.
  4. If the above conditions are false, meaning that either of root1 or root2 is empty, then return false.

Implementation for Symmetric Tree

C++ Program for Symmetric Tree
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// defining the tree node
class Node
{
    public : 
    int data;
    Node *left;
    Node *right;
    
    // constructor for initialization
    Node(int num)
    {
        data = num;
        left = right = NULL;
    }
};

/*utility function to check whether trees rooted at 
root1 and root2 are mirror images of each other or not */
bool utility(Node *root1, Node *root2) 
{ 
    /* base case : if both trees are empty then 
    they are mirror images of each other */
    if (root1 == NULL && root2 == NULL) 
        return true; 
  
    /* for trees rooted at root1 and root2 to be mirror images, 
    following conditions must be satisfied */
    if (root1 && root2) 
        /* Their root node's data must be same
        if this is not the case then immediately 
        return false */
        return root1->data == root2->data &&  
                
                /*left subtree of left tree and right s
                ubtree of right tree have to be mirror images*/
                utility(root1->left, root2->right) &&   
                
                    /*right subtree of left tree and left subtree 
                    of right tree have to be mirror images*/ 
                    utility(root1->right, root2->left); 
    
    
    /* This condition is reached when : 
    if only either of root1 or root2 is empty */
    
    return false; 
} 

/* function to check if tree 
rooted at root is Symmetric */
bool isSymmetric(Node* root) 
{ 
    // apply utility function to check if tree is mirror of itself 
    return utility(root, root); 
} 

// main function to implement above functions
int main() 
{
    /* construct the binary tree*/
    Node *root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(2);
    root->left->left = new Node(3);
    root->left->right = new Node(4);
    root->right->left = new Node(4);
    root->right->right = new Node(3);
    
    isSymmetric(root) ? cout<<"Symmetric Tree" : cout<<"Not Symmetric";
    
  return 0;
}
Symmetric Tree
Java program for Symmetric Tree
import java.io.*;
import java.util.*;

class tutorialCup 
{
    static class Node
    {
        int data;
        Node left;
        Node right;
        
        Node(int num)
        {
            data = num;
            left = right = null;
        }
    };
    
    /*utility function to check whether trees rooted at 
    root1 and root2 are mirror images of each other or not */
    static boolean utility(Node root1, Node root2) 
    { 
        /* base case : if both trees are empty then 
        they are mirror images of each other */
        if (root1 == null && root2 == null) 
            return true; 
      
        /* for trees rooted at root1 and root2 to be mirror images, 
        following conditions must be satisfied */
        if (root1 != null && root2 != null) 
            /* Their root node's data must be same
            if this is not the case then immediately 
            return false */
            return root1.data == root2.data &&  
                    
                    /*left subtree of left tree and right s
                    ubtree of right tree have to be mirror images*/
                    utility(root1.left, root2.right) &&   
                    
                        /*right subtree of left tree and left subtree 
                        of right tree have to be mirror images*/ 
                        utility(root1.right, root2.left); 
        
        
        /* This condition is reached when : 
        if only either of root1 or root2 is empty */
        
        return false; 
    } 
    
    /* function to check if tree 
    rooted at root is Symmetric */
    static boolean isSymmetric(Node root) 
    { 
        // apply utility function to check if tree is mirror of itself 
        return utility(root, root); 
    } 
    
    /* main function to implement above function */
    public static void main (String[] args) 
    {
        /* construct the binary tree*/
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(2);
        root.left.left = new Node(3);
        root.left.right = new Node(4);
        root.right.left = new Node(4);
        root.right.right = new Node(3);
        
        if(isSymmetric(root))
        System.out.println("Symmetric Tree");
        else System.out.println("Not Symmetric");
    }

}
Symmetric Tree

Complexity Analysis

  1. Time Complexity : T(n) = O(n)
  2. Space Complexity : A(n) = O(1) or O(log n), considering recursion stack space.

Iterative

Approach

The idea is to convert the recursive approach into iterative approach by using a Queue data structure by performing a breadth-first search(BFS)/level order traversal.  Again, We use 2 copies of the binary tree say, b1 and b2(to handle left and right subtree separately) and check if :

  1. root value of b1 and b2 are the same or not.
  2. left subtree of b1 and right subtree of b2 are the same(in terms structure as well as node values) or not.
  3. right subtree of b1 and left subtree of b2 are the same(in terms structure as well as node values) or not.

if conditions 1,2 and 3 are true Iteratively true for left and right subtrees we simply return true (else return false).

b1 and b2 have root1 and root2 as root node respectively.

Algorithm for Symmetric Tree

  1. Define base cases.
  2. Create a queue and push two copies of root (to handle left and right subtree) node into it.
  3. Begin The BFS traversal and at each iteration pop two nodes from the queue namely leftNode and rightNode.
    • if the value of both the nodes is not equal then return false (and terminate the traversal).
    • Then, if leftNode.left and rightNode.right both are not null, push them into the queue.
      • if only either of the above is not null then return false (and terminate the traversal).
    • Then, if leftNode.right and rightNode.left both are not null, push them into the queue.
      • if only either one of the above is not null then return false (and terminate the traversal).
  4. If the queue becomes empty, BFS is terminated and returns true.

Example 1

 

Example 2

  

Implementation for Symmetric Tree

C++ Program for Symmetric Tree
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// defining the tree node
class Node
{
    public : 
    int data;
    Node *left;
    Node *right;
    
    // constructor for initialization
    Node(int num)
    {
        data = num;
        left = right = NULL;
    }
};

/* function to check if tree 
rooted at root is Symmetric */
bool isSymmetric(Node* root) 
{
    /* base cases */
    
    // 1. if tree is empty it's symmetric
    if(root == NULL) 
        return true; 
    
    // 2. if tree has only one node, it's symmetric
    if(!root->left && !root->right) 
        return true; 
    
    // create queue for BFS traversal  
    queue <Node*> q; 
    
    /* root is inserted two times so that we can peform
    bi-directional BFS to check mirror image property
    which is basically a type of bilateral symmetry */
    q.push(root); 
    q.push(root); 
      
    /* these store nodes for bi-directional BFS traversal */
    Node* leftNode, *rightNode; 
      
    while(!q.empty())
    { 
        /* remove nodes to check if they are symmetric or not */ 
        leftNode = q.front(); 
        q.pop(); 
          
        rightNode = q.front(); 
        q.pop(); 
          
        /* if both left and right nodes exist but 
        have different, the tree is not symmetric */ 
        if(leftNode->data != rightNode->data) 
        return false; 
          
        /* Push left child of left subtree node 
        and right child of right subtree 
        node in queue */ 
        if(leftNode->left && rightNode->right)
        { 
            q.push(leftNode->left); 
            q.push(rightNode->right); 
        } 
          
        /* Else if only one child is present alone 
        and other is NULL, then tree is not symmetric */ 
        else if (leftNode->left || rightNode->right) 
        return false; 
          
        /* Push right child of left subtree node 
        and left child of right subtree node 
        in queue */ 
        if(leftNode->right && rightNode->left)
        { 
            q.push(leftNode->right); 
            q.push(rightNode->left); 
        } 
        /* Else if only one child is present alone 
        and other is NULL, then tree is not symmetric */ 
        else if(leftNode->right || rightNode->left) 
        return false; 
    } 
    
    /* the tree is symmetric if all the nodes 
    have been processed and queue becomes empty */
    
    return true; 
} 

// main function to implement above functions
int main() 
{
    /* construct the binary tree*/
    Node *root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(2);
    root->left->left = new Node(3);
    root->left->right = new Node(4);
    root->right->left = new Node(4);
    root->right->right = new Node(3);
    
    isSymmetric(root) ? cout<<"Symmetric Tree" : cout<<"Not Symmetric";
    
  return 0;
}
Symmetric Tree
Java program for Symmetric Tree
import java.io.*;
import java.util.*;

class tutorialCup 
{
    static class Node
    {
        int data;
        Node left;
        Node right;
        
        Node(int num)
        {
            data = num;
            left = right = null;
        }
    };
    
    /* function to check if tree 
    rooted at root is Symmetric */
    static boolean isSymmetric(Node root) 
    {
        /* base cases */
        
        // 1. if tree is empty it's symmetric
        if(root == null) 
            return true; 
        
        // 2. if tree has only one node, it's symmetric
        if(root.left == null && root.right == null) 
            return true; 
        
        // create queue for BFS traversal  
        Queue <Node> q = new LinkedList<>(); 
        
        /* root is inserted two times so that we can peform
        bi-directional BFS to check mirror image property
        which is basically a type of bilateral symmetry */
        q.add(root); 
        q.add(root); 
          
        /* these store nodes for bi-directional BFS traversal */
        Node leftNode, rightNode; 
          
        while(!q.isEmpty())
        { 
            /* remove nodes to check if they are symmetric or not */ 
            leftNode = q.poll();
            rightNode = q.poll();
              
            /* if both left and right nodes exist but 
            have different, the tree is not symmetric */ 
            if(leftNode.data != rightNode.data) 
            return false; 
              
            /* Push left child of left subtree node 
            and right child of right subtree 
            node in queue */ 
            if(leftNode.left != null && rightNode.right != null)
            { 
                q.add(leftNode.left); 
                q.add(rightNode.right); 
            } 
              
            /* Else if only one child is present alone 
            and other is NULL, then tree is not symmetric */ 
            else if (leftNode.left != null  || rightNode.right != null) 
            return false; 
              
            /* Push right child of left subtree node 
            and left child of right subtree node 
            in queue */ 
            if(leftNode.right != null && rightNode.left != null)
            { 
                q.add(leftNode.right); 
                q.add(rightNode.left); 
            } 
            /* Else if only one child is present alone 
            and other is NULL, then tree is not symmetric */ 
            else if(leftNode.right != null || rightNode.left != null) 
            return false; 
        } 
        
        /* the tree is symmetric if all the nodes 
        have been processed and queue becomes empty */
        
        return true; 
    } 

    
    /* main function to implement above function */
    public static void main (String[] args) 
    {
        /* construct the binary tree*/
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(2);
        root.left.left = new Node(3);
        root.left.right = new Node(4);
        root.right.left = new Node(4);
        root.right.right = new Node(3);
        
        if(isSymmetric(root))
        System.out.println("Symmetric Tree");
        else System.out.println("Not Symmetric");
    }

}
Symmetric Tree

Complexity Analysis

  1. Time Complexity : T(n) = O(n)
  2. Space Complexity : A(n) = O(n),queue is used.

References

Translate »