Binary Tree: Check if a binary tree is symmetric or mirror of itself using iterative approach

Property of Symmetric Binary Tree

The Left Subtree and the Right Subtree of a given node in a Symmetric Binary Tree are mirror images of each other

How to check if a tree is Symmetric or not?

We check if a tree is symmetric or not by comparing the left subtree of root with the right subtree and checking if all the nodes are mirror of themselves.
Using queue, we simply insert left and right node of root respectively and check whether they are equal or not and continue this process till whole tree is traversed.

Diagram

Algorithm

• Create queue say q and add left and right node of root respectively
• While queue is not empty
  • Remove two nodes and store into tempLeft and tempRight respectively
  • If tempLeft and tempRight both are NULL then continue
  • If (tempLeft is NULL and tempRight is not NULL) or (tempLeft is not NULL and tempRight is NULL), then return false
  • If tempLeft.data is not equal to tempRight.data, then return false
  • Now we are done with this level, we have to check next level
  • For this we have to insert left and right child of tempLeft and tempRight respectively back to the queue
  • Add left child of tempLeft
  • Add right child of tempRight
  • Add right child of tempLeft
  • Add left child of tempRight

Complexity

Time Complexity : O(n) , where n is the number of nodes in binary tree
Space Complexity: O(Height of Tree)

Java Code

import java.util.LinkedList;
    import java.util.Queue;
    
    class BinaryTreeCheckSymmetryIterative{
    
        static class Node {
         
            int data;
            Node left, right;
         
            Node(int element) {
                data = element;
                left = right = null;
            }
        }
        
        Node root;
    
        public static Node constructBinaryTree(int[] arr, int i) {
            
            Node root = null;
            
            if (i < arr.length) {
                root = new Node(arr[i]);
     
                root.left = constructBinaryTree(arr, 2 * i + 1);
                root.right = constructBinaryTree(arr, 2 * i + 2);
            }
            
            return root;
        }
     
        public boolean isSymmetric() {
     
            Queue q = new LinkedList<>();
     
            q.add(root.left);
            q.add(root.right);
     
            while (!q.isEmpty()) {
     
                Node tempLeft = q.remove();
                Node tempRight = q.remove();
     
                if (tempLeft == null && tempRight == null)
                    continue;
     
                if ((tempLeft == null && tempRight != null) ||
                        (tempLeft != null && tempRight == null))
                    return false;
     
                if (tempLeft.data != tempRight.data)
                    return false;
     
                q.add(tempLeft.left);
                q.add(tempRight.right);
                q.add(tempLeft.right);
                q.add(tempRight.left);
            }
     
            return true;
        }
     
        public static void main(String args[]) {
            
            BinaryTreeCheckSymmetryIterative bt = new BinaryTreeCheckSymmetryIterative();
            
            int[] bstElements = new int[] { 1, 2, 2, 3, 4, 4, 3 };
            bt.root = constructBinaryTree(bstElements, 0);
            
            boolean result = bt.isSymmetric();
            
            if (result == true) {
                System.out.println("Given Tree is Symmetric");
            } else {
                System.out.println("Given Tree is not Symmetric");
            }
        }
    
  }

Output

Given Tree is Symmetric