Sunday, 31 March 2019

Check if a Binary Tree is a Mirror Image or Symmetric in Java.

Check if a Binary Tree is a Mirror Image or Symmetric..

Check if a given binary tree is a symmetric or you can also say check whether tree is a mirror of itself (ie, symmetric around its center)

 Lets see sample input and output:

Algorithm 

Finding the tree is symmetric or not is very similar to a problem where we are given two trees and we are told to identify if they are mirror image of each other.

you may like to see,
  1. Check if two trees are mirror images of each other
  2. Check if two trees are identical or not

Considering the below example, if we break the tree into two subtrees around root node like below,(Two subtree root.left and root.right) 
 

             1
           /   \
          2     2
         / \   / \
        3   4 4   3
Left sub-tree 
        
          2    
         / \   
        3   4
Right sub-tree 
          2
         / \
        4   3
Now the problem is very similar to identify if both trees are mirror images of each other or not,
Please refer detailed post on Check a given two Binary Trees are Mirror Image of each other

Do preorder traversal in both the trees and check if data of left child of tree1 is matching with data at right child of tree2, if this holds tree for all the nodes of the tree1 and tree2 then both trees are mirror image of each other else not.



Java Program to check if a Binary Tree is Symmetric or not. 



  CheckSymmetricBinaryTree.java

package com.javabypatel.binarytree;

import java.util.LinkedList;
import java.util.Queue;

/*
              50
           /     \
         20      20
        / \     /  \
      10  30  30   10
 */
public class CheckSymmetricBinaryTree {
    private static Node rootNode;

    public static void main(String[] args) {

        addNodeInBinaryTree(rootNode, 50);
        addNodeInBinaryTree(rootNode, 20);
        addNodeInBinaryTree(rootNode, 20);
        addNodeInBinaryTree(rootNode, 10);
        addNodeInBinaryTree(rootNode, 30);
        addNodeInBinaryTree(rootNode, 30);
        addNodeInBinaryTree(rootNode, 10);

        printTreeLevelOrder(rootNode);

        if (rootNode != null)
            System.out.println(isSymmetric(rootNode.getLeft(), rootNode.getRight()));
    }

    private static boolean isSymmetric(Node tree1, Node tree2) {
        if (tree1 == null && tree2 == null) { //Both trees are NULL
            return true;
        }
        if (tree1 == null || tree2 == null) { //Any one of the Tree is NULL
            return false;
        }
        if (tree1.getData() != tree2.getData()) { // Data check
            return false;
        }

        boolean leftCheck = isSymmetric(tree1.getLeft(), tree2.getRight());
        boolean rightCheck = isSymmetric(tree1.getRight(), tree2.getLeft());

        if (leftCheck && rightCheck) {
            return true;
        } else {
            return false;
        }
    }

    //Iterative way of adding new Node in Binary Tree.
    private static void addNodeInBinaryTree(Node root, int data) {

        if (root == null) {
            // No Nodes are Present, create one and assign it to rootNode
            rootNode = new Node(data);

        } else {
            //Nodes present, So checking vacant position for adding new Node in sequential fashion
            //Start scanning all Levels (level by level) of a tree one by one until we found a node whose either left or right node is null.
            //For each and every node, we need to check whether Left and Right Node exist?
            //If exist, then that node is not useful for adding new node but we need to store left and right node of that node for later processing
            //that is why it is stored in Queue for sequential placement.
            //If not exist, then we found a node, where new node will be placed but not sure on left or right, so check which side is null and place new node there.

            Queue<Node> q = new LinkedList<Node>();
            q.add(root);
            while (!q.isEmpty()) {
                Node node = q.poll();

                if (node.getLeft() != null && node.getRight() != null) {
                    q.add(node.getLeft());
                    q.add(node.getRight());
                } else {
                    if (node.getLeft() == null) {
                        node.setLeft(new Node(data));
                    } else {
                        node.setRight(new Node(data));
                    }
                    break;
                }
            }
        }

    }

    private static void printTreeLevelOrder(Node rootNode) {
        if (rootNode == null)
            return;

        Queue<Node> q = new LinkedList<Node>();
        q.add(rootNode);

        while (!q.isEmpty()) {
            Node node = q.poll();
            System.out.print(node.getData() + " ");

            if (node.getLeft() != null)
                q.add(node.getLeft());

            if (node.getRight() != null)
                q.add(node.getRight());
        }

    }
}









 


Node.java



package com.javabypatel.binarytree;

class Node {
    private int data;
    private Node left;
    private Node right;
 
    public Node(int data) {
        this.data = data;
    }
 
    public int getData() {
        return data;
    }
 
    public void setData(int data) {
        this.data = data;
    }
 
    public Node getLeft() {
        return left;
    }
 
    public void setLeft(Node left) {
        this.left = left;
    }
 
    public Node getRight() {
        return right;
    }
 
    public void setRight(Node right) {
        this.right = right;
    }
}

















at




















No comments:
















Post a Comment