Check given binary tree is mirror or symmetric tree (Java/ recursive /example)

• Given two binary trees, check whether one binary tree is mirror/symmetric of another binary tree.
  • Traverse the binary trees using depth first search (DFS)  recursive algorithm.
• Binary tree and corresponding mirror (image) binary tree are shown in Fig 1.

Algorithm – check one binary tree is mirror of another tree (recursive).

1. Check If both input trees (tree1 & tree2) are null
   • Successfully traversed binary trees, return true.
2. If any of the input trees is null
   • tree1 is not mirror of other tree2, return false.
3. Evaluate the Current Node
4. Compare the data of binary trees, tree1 & tree2
   • If Data is same for both nodes [Success condition]
     • Traverse Left child of tree1 and right child of tree2.
     • Traverse right child of tree1 and left child of tree2.
   • else, data of both nodes are not same
     • Trees are not mirror trees, return false.
5. At end of traversal, we will know whether one tree is mirror of another tree.

Program : check binary trees are mirror image of each other using java

1.) IsMirrorTree Class:

• IsMirrorTree class is used to check one binary tree is mirror of another binary tree.
• Traverse the binary tree using recursive algorithm.

package org.learn.Question;

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

public class IsMirrorTree {
 public static boolean isMirrorTree(Node tree, Node mirrorTree) {
  if( null == tree && null == mirrorTree) 
   return true;
  
  if( null == tree || null == mirrorTree) 
   return false;
  
  if(tree.data != mirrorTree.data)
   return false;
  
  if(false == isMirrorTree(tree.left,mirrorTree.right))
   return false;
  
  if(false ==  isMirrorTree(tree.right,mirrorTree.left))
   return false;
  
  return true;
 }
 
 public static void printTree(Node root) {
  if (root == null) {
   System.out.println("Tree is empty");
   return ;
  }
  Queue<Node> queue = new LinkedList<Node>();
  queue.offer(root);
  while (!queue.isEmpty()) {
   Node node = queue.poll();   
   System.out.printf("%d ",node.data);  
   if (node.left != null) {
    queue.offer(node.left);
   }
   if (node.right != null) {
    queue.offer(node.right);
   }
  }
  System.out.println(""); 
  return;
 }
}

2.) Node:

• Node class representing the nodes in a binary tree.

package org.learn.Question;

public class Node {
 public int data;
 public Node left;
 public Node right;

 public Node(int num) {
  this.data = num;
  this.left = null;
  this.right = null;
 }

 public Node() {
  this.left = null;
  this.right = null;
 }
 
 public static Node createNode(int number) {
  return new Node(number);
 }
}

3.) App Class:

• We are the creating binary tree in main method.
• We are calling IsMirrorTree class, to check one binary tree is mirror  of another binary tree.

package org.learn.Client;

import org.learn.Question.IsMirrorTree;
import org.learn.Question.Node;

public class App {
 public static void main(String[] args) {
  // Binary Tree 1:
  // root level 0
  Node A = Node.createNode(70);
  // Level 1
  Node B = Node.createNode(50);
  Node C = Node.createNode(55);
  // Level 2
  Node D = Node.createNode(25);
  Node E = Node.createNode(80);
  Node F = Node.createNode(37);
  Node G = Node.createNode(45);

  // connect Level 0 and 1
  A.left = B;
  A.right = C;
  // connect level 1 and level 2
  B.left = D;
  B.right = E;
  C.left = F;
  C.right = G;

  //Binary Tree 2:
  
  // root level 0
  Node P = Node.createNode(70);
  // Level 1
  Node Q = Node.createNode(55);
  Node R = Node.createNode(50);
  // Level 2
  Node S = Node.createNode(45);
  Node T = Node.createNode(37);
  Node U = Node.createNode(80);
  Node V = Node.createNode(25);

  // connect Level 0 and 1
  P.left = Q;
  P.right = R;
  // connect level 1 and level 2
  Q.left  = S;
  Q.right = T;
  R.left  = U;
  R.right = V;

  System.out.println("Binary Tree 1 :");
  IsMirrorTree.printTree(A);
  System.out.println("Binary Tree 2 :");
  boolean isMirrorBinaryTrees = IsMirrorTree.isMirrorTree(A,P);
  System.out.printf("Check Trees are mirror binary tree : %b",isMirrorBinaryTrees);
 }
}

Output : check binary tree is symmetric of another binary tree using java

Binary Tree 1 :
70 50 55 25 80 37 45 
Binary Tree 2 :
70 55 50 45 37 80 25 
Check Trees are mirror binary tree : true

Download code – check trees are mirror binary tree using java