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

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

Comparing if nodes are mirror

• Traverse the tree in Inorder[left root right] and simultaneously traverse the tree in mirror of Inorder[right root left], taking one step at a time
• Check if the current node from Inorder has same data as the node from mirror Inorder
  • If same data: check it's children nodes
  • Else: return false
• If all nodes are visited return true

To solve this problem we have to traverse the tree and tree traversal can be done in two ways: Iterative and Recursive.
In this article we will be going through the Recursive approach

Diagram

Example 1:                                                                  

 

Example 2:

Complexity:

As we are simply traversing the tree the Time Complexity and Space Complexity will be the same as that of traversing a Tree

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

The Time Complexity will be O(N) as we have to check each node at least once and the space complexity will be
O(Height of Tree) which is O(logN) for a perfect binary tree, the Space Complexity is because
of the stack memory consumed by the recursive calls

Java Code

class BinaryTreeCheckSymmetry{
	
        static class Node {
            // Node class for Binary Search Tree
            int data;
            Node left, right;
    
            // Constructor to set the value of the node
            Node(int data) {
                this.data = data;
                this.left = null;
                this.right = null;
            }
        }
    
        // Function to check if a given tree is symmetric or not
        static boolean isSymmetric(Node root) {
             // Edge Case: A empty tree is said to be symmetric
             if (root == null) {
                 return true;
             }
    
             return isMirror(root, root);
        }
    
        static boolean isMirror(Node node1, Node node2) {
                // Base Case: if both the subtree roots are null
                if (node1 == null && node2 == null) {
                    return true;
                }
                
                // We Recursively traverse the tree for both the roots
                // Check if both the roots value are same or not
                if (node1 != null && node2 != null && node1.data == node2.data) {
                    // We have to check for both the sides,
                    // for node1 of left with node2 right and node1 of right with the node2 of 
                    // left
                    return isMirror(node1.left, node2.right) && isMirror(node1.right, node2.left);
                }
    
                // If above cases are not true, then we return false
                return false;
        }
    
        public static void main(String[] args) {
            // Example 1:
            Node tree1 = new Node(1);
            tree1.left = new Node(2);
            tree1.right = new Node(2);
            tree1.left.left = new Node(3);
            tree1.left.right = new Node(4);
            tree1.right.left = new Node(4);
            tree1.right.right = new Node(3);
    
            if (isSymmetric(tree1)) {
                System.out.println("The Example 1 is Symmetric");
            } else {
                System.out.println("The Example 1 is Not Symmetric");
            }
    
            // Example 2:
            Node tree2 = new Node(1);
            tree2.left = new Node(2);
            tree2.right = new Node(2);
            tree2.left.right = new Node(3);
            tree2.right.right = new Node(3);
    
            if (isSymmetric(tree2)) {
                System.out.println("The Example 2 is Symmetric");
            } else {
                System.out.println("The Example 2 is Not Symmetric");
            }
       }
  }

Output

The Example 1 is Symmetric
The Example 2 is Not Symmetric