Check for Symmetric Binary Tree (Iterative Approach) in Java

By Aditya Goyal

In this tutorial, will see how we can check for a Symmetric Binary Tree in Java. A Symmetric Binary Tree is a tree in which a tree is a mirror of itself. We will be doing this code without recursion.

For Example: –

     9
   /   \
  5     5
 / \   / \
2   1 1   2

This is an example of a symmetric binary tree.

In this, we will be using a queue. So, in this we see each level behaves like a palindrome. As we can see, the left child of our left subtree is equal to the right child of the right subtree and vice-versa. So we will be inserting these into the queue and check whether they are equal or not.

Code: –

import java.util.* ; 
public class Main 
{ 
    Node r; 
    static class Node 
    { 
        int data; 
        Node left;
        Node right; 
        Node(int data) 
        { 
            this.data = data; 
            left = null; 
            right = null; 
        } 
    } 
    Main(Node r){
        this.r = r; 
    } 
    public boolean symmetric(Node root) 
    { 
        //Add null elements to the queue
        Queue<Node> queue = new LinkedList<Node>(); 
        //Add left right nodes
        queue.add(r.left); 
        queue.add(r.right); 
        while (!queue.isEmpty()) 
        { 
            // Remove and check last 2 nodes
            Node tleft = queue.remove(); 
            Node tright = queue.remove(); 
            // both null check more
            if (tleft==null && tright==null) {
                continue;
            } 
            // If any of the one is null then false
            if ((tleft==null && tright!=null) || (tleft!=null && tright==null)) {
                return false;
            } 
            // If both not equal false
            if (tleft.data != tright.data) {
                return false;
            } 
            queue.add(tleft.left); // First we add left child left subtree
            queue.add(tright.right); // Than we add right child right subtree
            queue.add(tleft.right); // Than right child left subtree
            queue.add(tright.left); // At last left child right subtree
        } 
        return true; 
    } 
    public static void main(String[] args) 
    { 
        Node node = new Node(9); 
        Main tree = new Main(node); 
        tree.r.left = new Node(5); 
        tree.r.right = new Node(5); 
        tree.r.left.left = new Node(2); 
        tree.r.left.right = new Node(1); 
        tree.r.right.left = new Node(1); 
        tree.r.right.right = new Node(2); 
  
        if (tree.symmetric(tree.r)) {
            System.out.println("Symmetric");
        } 
        else{
            System.out.println("Not Symmetric");
        } 
    } 
}

Output: –

Symmetric

This is how we check for a symmetric binary tree with Java.

Also Read: –

Leave a Reply