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:

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.
identical binary tree ismorphic
Fig 1: Identical 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.
isomorphic binary tree
Fig 2: Example of isomorphic binary tree

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

  • The structure of binary trees is not same
  • Binary trees are not isomorphic.
Trees are not isomorphic
Fig 3: 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

 

Scroll to Top