Check for Symmetric Binary Tree (Iterative Approach) in Java
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