Is a Tree Symmetric?

Given a binary tree find out if it is symmetric or not.

A tree is symmetric if it is left sub tree is a reflection of its right sub tree.

Note that symmetry doesn’t mean left sub tree is equal to right sub tree.

The following tree is a symmetric tree:

As you see the left subtree is not equal to right subtree,

but it is a mirror reflection.

Try out the solution here:

https://leetcode.com/problems/symmetric-tree/

Solution:

To find out if a tree is symmetric or not , you need to make sure of the following things

• The right tree of the left subtree is equal to the left tree of the right subtree.

• The left tree of the left subtree is equal to the right tree of the right subtree.
• The left subtree and the right subtree are equal

We can solve this either using recursion or iteratively using queue.

Approach 1: Using Recursion

Here is the recursive code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        
        return isMirror(root.left,root.right);
        
    }
    
    
    public boolean isMirror(TreeNode left,TreeNode right){
        
        
        if(left == null && right == null) return true;
        
        if(left == null || right == null) return false;
        
        return (left.val == right.val) && isMirror(left.right,right.left) && isMirror(left.left,right.right);
        
    }
}

You pass the left subtree and the right subtree to a recursive function.

The function checks if both of them are null , then it returns true.

If any one of them is null and not the other , then it is not symmetric so return false.

Then check the three conditions we earlier mentioned.

We check if left tree of right subtree is equal to right tree of left subtree recursively.

And if left tree of left subtree is equal to right tree of right subtree recursively.

Both of them should match along with:

Left node should be equal to right node.

Time complexity:

We iterate through all the nodes so time complexity is O(n)

Space complexity:

For the worst case (a linear tree) we need to make recursive calls for each node so space complexity is O(n)

Approach 2 – Using iteration (Queues)

In this approach we implement the same logic used in recursing using queues.

here is the code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        

        
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        
        queue.add(root.left);
        
        queue.add(root.right);
        
        
        while(!queue.isEmpty()){
            
            
            TreeNode left = queue.poll();
            
            TreeNode right = queue.poll();
            
            
            
            if(left == null && right == null) continue;
            
            if(left == null || right == null) return false;
            
            if(left.val != right.val) return false;
            queue.add(left.right);
            queue.add(right.left);
            
            queue.add(left.left);
            queue.add(right.right);
            
        }
        return true;
    }
}

We initially push the left node and the right node into the queue.

And then while the queue is not empty:

We pop out the first two nodes (left and right)

And we check if both are null , if so we go back to popping the next two.

Else if any one of them is null and not the other , we return false.

Else we push the right node of left node first , then the left node of right node.

And then we push the left node of left node and the right node of right node.

This way the iteration continues for the rest of the nodes.

Time complexity:

Time complexity remains the same since we iterate through all the nodes.O(n)

Space complexity:

Since we use a queue which stores all the nodes ,the space complexity is O(n)

That’s it!