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.
  • 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.
idential tree quasi isomorphic
Fig 1: Identical binary trees

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.
Fig 2: Mirror binary trees

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.
Non quasi isomorphic binary tree
Fig 3: Trees are not quasi- isomorphic

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

identical mirror tree quasi isomorphic
Fig 4: Identical & mirror binary trees
  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)

 

Scroll to Top