1. Introduction

Given the root of a binary tree, check whether it is a mirror of itself (symmetric around its center).

2. Content

If the tree is mirrored from its root, then the left subtree and right subtree must be structurally identical. Also, the node values must be the same. I will show the recursive and iterative way to solve this problem. But first let us look on few examples and understand what is symmetric tree.

Example 1: The Below binary tree is symmetric.

Example 2: The below binary tree is a symmetric.

Example 3: The below binary tree is not symmetric.

In the left subtree, Node 2 has the left child as 3. Same with the right subtree. For the tree to be symmetric, the right subtree’s Node 2 should have had Node 3 as its right child.

3. Recursive approach

The idea here is recursively check the left subtree and right subtree by comparing their opposite sides.

1. Method signature

public boolean isSymmetric(TreeNode root) {

}

2. Let us create a method called as is isSymmetric with two parameters as below:

private boolean isSymmetric(TreeNode leftNode, TreeNode rightNode) {

}

We can use this method as below:

public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return isSymmetric(root.left, root.right);
}

3. If leftNode and rightNode are null, then we know it is symmetric. It is not symmetric if either is null or their values are not equal. If the values of leftNode and rightNode are the same, then only compare (left and right subtree) and (right and left subtree).

private boolean isSymmetric(TreeNode leftNode, TreeNode rightNode) {
    if(leftNode == null && rightNode == null) return true;
        
    if(leftNode == null || rightNode == null) return false;
        
    if(leftNode.val == rightNode.val) {
        return isSymmetric(leftNode.left, rightNode.right)
                && isSymmetric(leftNode.right, rightNode.left);
    }       
    return false;
}

4. Entire implementation

public boolean isSymmetric(TreeNode root) {
    if(root == null) return true;
    return isSymmetric(root.left, root.right);
}
    
private boolean isSymmetric(TreeNode leftNode, TreeNode rightNode) {
    if(leftNode == null && rightNode == null) return true;
        
    if(leftNode == null || rightNode == null) return false;
        
    if(leftNode.val == rightNode.val) {
        return isSymmetric(leftNode.left, rightNode.right)
                && isSymmetric(leftNode.right, rightNode.left);
    }       
    return false;
}

Time and Space complexity nomenclature: n is the total number of nodes in the tree.

Time complexity: O(n) because we need to traverse the entire tree to check for symmetricity. 

Space complexity: O(n) because the recursion tree for unbalanced tree can degrade to the total number of nodes in the tree.

4. Iterative approach

For an iterative approach, we will use BFS or Breadth First Search using auxiliary data structure Queue. Below is the code for the iterative approach:

public boolean isSymmetric(TreeNode root) {
        
    if(root == null) return true;
        
    Deque<TreeNode> q = new LinkedList<>();
    q.add(root);
    q.add(root);
        
    while(!q.isEmpty()) {
        TreeNode leftNode = q.poll();
        TreeNode rightNode = q.poll();
        if(leftNode == null && rightNode == null) continue;
        if(leftNode == null || rightNode == null) return false;
        if(leftNode.val != rightNode.val) return false;
            
        q.add(leftNode.left);
        q.add(rightNode.right);
            
        q.add(leftNode.right);
        q.add(rightNode.left);
    }
    return true;
}

Time and Space complexity nomenclature: n is the total number of nodes in the tree.

Time complexity: O(n) because we need to traverse the entire tree to check for symmetricity. 

Space complexity: O(n) because we are saving all nodes of the tree in Queue.

5. Conclusion

In this article, we saw how to check if a binary tree is a mirror of itself using Recursion and Iteration.

GitHub Link: https://github.com/savanibharat/justamonad-tutorials/blob/master/justamonad-tutorials-leetcode/src/main/java/com/justamonad/tutorials/leetcode/tree/SymmetricTree.java