Check binary tree is Quasi-Isomorphic of other tree in java (DFS / Example)

• Given two binary trees, find out one binary tree is Quasi Isomorphic of other binary tree.
• Traverse the binary tree using depth first search (DFS) recursive algorithm.
• What is Quasi Isomorphic tree?
  • Trees having identical structure or obtained by swapping (or mirror binary tree) its children are called Quasi isomorphic trees.
  • In quasi isomorphic trees, we are concerned about structures only (we will not consider data of nodes).
• Tree will be quasi isomorphic if any subtree satisfies either of following conditions.
  • Identical binary tree: Structure of one subtree tree is identical to another subtree.
  • Mirror binary tree: Structure of one subtree is mirror of another subtree.
• We have already discussed similar problem Check whether binary trees are Isomorphic.

Example – Quasi-isomorphic binary trees in java.

Example 1: Given two Identical binary trees in java (Fig 1).

• Tree shown in Fig 1 have identical structure.
  • Ignore the data of respective nodes.
• Binary trees are quasi-isomorphic.

Example 2: Binary tree & mirror binary trees in java.

• One tree is mirror of another binary tree shown in Fig 2.
  • Ignore the data of respective nodes.
• Binary trees are quasi-isomorphic.

Example 3: One binary tree is not quasi-isomorphic of other binary tree.

• One tree (or subtree) is neither identical nor mirror to another binary tree.
• Trees are not quasi-isomorphic.

Example 4: Quasi-Isomorphic binary trees are shown (Fig 4)

1. Nodes A, B, C  & Nodes P,Q,R of tree1 & tree2 are identical subtree trees.
2. Nodes D, G, H & Nodes S,V,W of tree1 & tree2 are identical subtree trees.
3. Nodes C, E, F, I ,J & Nodes R,T,U,X,Y of tree1 & tree2 are mirror subtree of binary trees.
4. Both trees are quasi-isomorphic.

Algorithm: check whether binary trees are quasi isomorphic (recursive).

• Evaluate the Current Nodes of tree1 & tree2
• If any of the tree is null
  • Trees are not quasi isomorphic & return false
• Check both trees tree1 and tree2
  • if tree1 and tree2 are null,  traversal completed successfully.
  • return true
• Let us check if trees are identical binary trees
  • Traverse Left subtree of tree1 and left subtree of tree2
  • Traverse Right subtree of tree1 and right subtree of tree2
  • If structures are identical, then return true
• If trees are not identical, let us check one tree (or subtree) are mirror of other tree (subtree)
  • Traverse Left subtree of tree1 and right subtree of tree2
  • Traverse Right subtree of tree1 and left subtree of tree2
  • If structures are mirror structure, then return true
  • Else, return false
• At the end of traversal, we will know whether trees are quasi isomorphic

Program – check binary trees are quasi isomorphic (recursive algorithm)

1.) QuasiIsomorphicBinaryTree :

• QuasiIsomorphicBinaryTree class is responsible for checking that binary trees are Quasi Isomorphic.

package org.learn.Question;

public class QuasiIsomorphicBinaryTree {
	
	public static boolean quasiIsomorphicBinaryTree(Node tree1, Node tree2) {
		if(tree1 == null && tree2 == null) {
			return true;
		}
		
		if(tree1 == null || tree2 == null) {
			return false;
		}
		
		//Check identical case
		if(quasiIsomorphicBinaryTree(tree1.left,tree2.left) 
				&& quasiIsomorphicBinaryTree(tree1.right,tree2.right))
			return true;
		
		//Check mirror case
		if(quasiIsomorphicBinaryTree(tree1.left,tree2.right) 
				&& quasiIsomorphicBinaryTree(tree1.right,tree2.left))
			return true;
		
		return false;
	}
}

2.) App Class:

• We are constructing binary trees in main method
• We are invoking quasiIsomorphicBinaryTree method to check whether trees are quasi isomorphic.

package org.learn.Client;

import org.learn.Question.Node;
import org.learn.Question.QuasiIsomorphicBinaryTree;

public class App 
{
	public static void main( String[] args )
    {		
		//level 0
		Node tree1 = Node.createNode(45); //A
		//level 1
		tree1.left = Node.createNode(20); //B
		tree1.right = Node.createNode(65);//C
		// left sub tree
		tree1.left.left = Node.createNode(49);//D
		tree1.left.left.left = Node.createNode(30);//G
		tree1.left.left.right = Node.createNode(45); //H

		// right subtree
		tree1.right.left = Node.createNode(30); //E
		tree1.right.right = Node.createNode(60);//F
		
		tree1.right.right.left = Node.createNode(65);//I	
		tree1.right.right.right = Node.createNode(55);//J	
		
		
		Node tree2 = Node.createNode(70); //P
		//level 1
		tree2.left = Node.createNode(55); //Q
		tree2.right = Node.createNode(85);//R
		// left sub tree
		tree2.left.left = Node.createNode(30);//S
		tree2.left.left.left = Node.createNode(80);//T
		tree2.left.left.right = Node.createNode(30); //U

		// right subtree
		tree2.right.left = Node.createNode(40); //V
		tree2.right.right = Node.createNode(65); //W
		tree2.right.left.left = Node.createNode(52); //X
		tree2.right.left.right = Node.createNode(10); //Y

		boolean isSame = QuasiIsomorphicBinaryTree.quasiIsomorphicBinaryTree(tree1, tree2);
		if(isSame) {
			System.out.println("Binary trees are Quasi-Isomorphic");
		} else {
			System.out.println("Binary trees are not Quasi-Isomorphic");
		}
    }
}

3.) Node class :

• Node class representing the nodes of 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 binary trees are quasi isomorphic in java

Binary trees are Quasi-Isomorphic

Download Code – Quasi-Isomorphic binary trees (recursive algorithm)