Check given binary trees are Isomorphic in java (recursive / examples)

• Given two binary trees, find out one binary tree is Isomorphic of another binary tree.
• Traverse the binary tree using depth first search (DFS) recursive algorithm.
• What is Isomorphic binary tree?
  • As per english dictionary, isomorphic is “being of identical or similar form, shape, or structure”.
  • If given binary tree have identical or similar form or shape or structure to another binary tree, then trees are isomorphic trees
  • The focus point is only structure of trees and we are not concerned about the data of any node.
• We have already discussed similar problems:
  • Find two binary trees are equal or identical or same
  • Find binary trees are mirror of each other.
  • Check binary tree is Quasi-Isomorphic of other binary tree (DFS / Example)

Examples – Check given binary tree is Isomorphic of other binary tree in java

Example 1: check binary trees are Isomorphic shown in Fig 1.

• The structure of both binary trees is same.
  • E.g Node B (tree1) and its corresponding Node Q (tree2) have two children. S
• Similarly, we can evaluate the all nodes of binary trees.

Example 2: check binary trees are Isomorphic shown in Fig 2.

• We can see that structure of both binary trees is same.
  • Binary trees are isomorphic binary trees.

Example 3: check binary trees are Isomorphic shown in Fig 3.

• The structure of binary trees is not same
• Binary trees are not isomorphic.

Conclusion: If structure (We will ignore data of nodes) of binary trees is same then binary tree are isomorphic.

Algorithm – check binary trees are Isomorphic.

• Check both trees, tree1 and tree2 for null
  • if tree1 and tree2 is null
    • Successfully complete traversal & return true
• If either tree1 or tree2 is null
  • Trees are not isomorphic and return false.
• Traverse left & right subtree of current node
  • Traverse left subtree of tree1 & left subtree of tree2
  • Traverse right subtree of tree1 and right subtree of tree2
• At end of traversal, we will know whether trees are isomorphic.

Program – find if given binary trees are Isomorphic using java

1.) IsomorphicBinaryTree Class: 

• IsomorphicBinaryTree class is responsible for finding that binary trees are isomorphic using depth first search (recursive) algorithm.

package org.learn.Question;

public class IsomorphicBinaryTree {

	public static boolean isIsomorphicBinaryTree(Node tree1, Node tree2) {

		if (tree1 == null && tree2 == null) {
			return true;
		}

		if (tree1 == null || tree2 == null) {
			return false;
		}

		if (false == isIsomorphicBinaryTree(tree1.left, tree2.left))
			return false;

		if (false == isIsomorphicBinaryTree(tree1.right, tree2.right))
			return false;

		return true;
	}
}

2.) App Class:

•  We are constructing both binary trees in main method.
• We are calling method of IsomorphicBinaryTree class, to check whether binary trees are isomorphic.

package org.learn.Client;

import org.learn.Question.IsomorphicBinaryTree;
import org.learn.Question.Node;

public class App 
{
	public static void main( String[] args )
    {		
		Node tree1 = Node.createNode(50);
		tree1.left = Node.createNode(30);
		tree1.right = Node.createNode(30);
		// left sub tree
		tree1.left.left = Node.createNode(40);
		tree1.left.right = Node.createNode(10);

		// right subtree
		tree1.right.left = Node.createNode(30);
		tree1.right.right = Node.createNode(60);
		
		Node tree2 = Node.createNode(10);
		tree2.left = Node.createNode(40);
		tree2.right = Node.createNode(20);
		// left sub tree
		tree2.left.left = Node.createNode(50);
		tree2.left.right = Node.createNode(15);

		// right subtree
		tree2.right.left = Node.createNode(70);
		tree2.right.right = Node.createNode(60);

		boolean isSame = IsomorphicBinaryTree.isIsomorphicBinaryTree(tree1, tree2);
		if(isSame) {
			System.out.println("Binary trees are Isomorphic");
		} else {
			System.out.println("Binary trees are not Isomorphic");
		}
    }
}

3.) Node Class :

• Node class is representing the nodes of 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);
	}
}

Output – check given binary trees (Fig 1) are Isomorphic using java

Binary trees are Isomorphic

Download code – isomorphic binary trees in java