CC-14 : Check if a given Binary Tree is a subtree of another Binary Tree.

Description:

A Binary Tree t1 a subtree of another Binary Tree bt2, if the root and all its sub nodes of t1 matches with a Tree Node t2 and all its sub nodes. Given 2 Binary Trees, check if the second Binary Tree t2 is a subtree of the first Binary Tree t1.

Test cases and expected outputs:

Input Parameters	Expected outputs
	Orig tree inOrder 33,6,5,78,4,8,14,9,18,16,7, toCheck tree inOrder 33,6,5,78, Orig tree preOrder 4,5,6,33,78,7,14,8,16,18,9, toCheck tree preOrder 5,6,33,78, Is Check1 subtree of Orig tree: true

Pseudocode:

Traverse Binary Tree T1 in via In-order traversal and store the result in a String. Traverse Binary Tree T2 via In-order traversal and store the result in a String.

If In-order traversal of t2 is not a substring of In-order traversal of t2, return false.

Traverse Binary Tree T1 in via Pre-order traversal and store the result in a String. Traverse Binary Tree T2 via Pre-order traversal and store the result in a String.

If Pre-order traversal of t2 is not a substring of Pre-order traversal of t2, return false.

If In-order and Pre-Order Traversals of t2 are substrings of In-order and Pre-Order Traversals of t1, return true.

Code:

public class BinTreeCheckSubtree
{
private StringBuilder traversal;

public boolean isSubtree(BinTreeNode root1, BinTreeNode root2) {
	traversal=new StringBuilder();
	inOrderRecursive(root1);
	String tree1InOrder=traversal.toString();
	System.out.println("Orig tree inOrder"+tree1InOrder);
	
	
	traversal=new StringBuilder();
	inOrderRecursive(root2);
	String tree2InOrder=traversal.toString();
	System.out.println("toCheck tree inOrder"+tree2InOrder);
	if (tree1InOrder.indexOf(tree2InOrder)==-1) {return false;}
	
	traversal=new StringBuilder();
	preOrderRecursive(root1);
	String tree1PreOrder=traversal.toString();
	System.out.println("Orig tree preOrder"+tree1PreOrder);
	traversal=new StringBuilder();
	preOrderRecursive(root2);
	String tree2PreOrder=traversal.toString();
	System.out.println("toCheck tree preOrder"+tree2PreOrder);
	if (tree1PreOrder.indexOf(tree2PreOrder)==-1) {return false;}
	return true;
}

public void inOrderRecursive(BinTreeNode parent){
	if (parent==null) {return;}
	inOrderRecursive(parent.getLeftChild());
	traversal.append(parent.getNodeData()).append(",");
	inOrderRecursive(parent.getRightChild());
}

public void preOrderRecursive(BinTreeNode parent){
	if (parent==null) {return;}
	traversal.append(parent.getNodeData()).append(",");
	preOrderRecursive(parent.getLeftChild());
	preOrderRecursive(parent.getRightChild());
}
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

Note: for easy reference BinTreeNode is included as internal class in program below. Ideally it should be in a separate file.

public class BinTreeCheckSubtree
{
private StringBuilder traversal;

public boolean isSubtree(BinTreeNode root1, BinTreeNode root2) {
	traversal=new StringBuilder();
	inOrderRecursive(root1);
	String tree1InOrder=traversal.toString();
	System.out.println("Orig tree inOrder"+tree1InOrder);
	
	
	traversal=new StringBuilder();
	inOrderRecursive(root2);
	String tree2InOrder=traversal.toString();
	System.out.println("toCheck tree inOrder"+tree2InOrder);
	if (tree1InOrder.indexOf(tree2InOrder)==-1) {return false;}
	
	traversal=new StringBuilder();
	preOrderRecursive(root1);
	String tree1PreOrder=traversal.toString();
	System.out.println("Orig tree preOrder"+tree1PreOrder);
	traversal=new StringBuilder();
	preOrderRecursive(root2);
	String tree2PreOrder=traversal.toString();
	System.out.println("toCheck tree preOrder"+tree2PreOrder);
	if (tree1PreOrder.indexOf(tree2PreOrder)==-1) {return false;}
	return true;
}

public void inOrderRecursive(BinTreeNode parent){
	if (parent==null) {return;}
	inOrderRecursive(parent.getLeftChild());
	traversal.append(parent.getNodeData()).append(",");
	inOrderRecursive(parent.getRightChild());
}

public void preOrderRecursive(BinTreeNode parent){
	if (parent==null) {return;}
	traversal.append(parent.getNodeData()).append(",");
	preOrderRecursive(parent.getLeftChild());
	preOrderRecursive(parent.getRightChild());
}
 	
public static void main(String[] args) {
	/**********************
 	Test cases given below
	 ********************/
	boolean retVal;
	try {
	BinTreeCheckSubtree chk=new BinTreeCheckSubtree();
	BinTreeNode root=chk.new BinTreeNode(4);
	//Left L1 Children
	root.setLeftChild(chk.new BinTreeNode(5));
	root.setRightChild(chk.new BinTreeNode(7));
	
	//Left L2 Children
	root.getLeftChild().setLeftChild(chk.new BinTreeNode(6));
	root.getLeftChild().setRightChild(chk.new BinTreeNode(78));
	
	//Left L3 Children
	root.getLeftChild().getLeftChild().setLeftChild(chk.new BinTreeNode(33));
	
	//Right L2 Children
	root.getRightChild().setLeftChild(chk.new BinTreeNode(14));
	
	
	//Right L3 Children
	root.getRightChild().getLeftChild().setLeftChild(chk.new BinTreeNode(8));
	root.getRightChild().getLeftChild().setRightChild(chk.new BinTreeNode(16));
	
	//Right L3 Children
	root.getRightChild().getLeftChild().getRightChild().setLeftChild(chk.new BinTreeNode(18));
	
	//Right L4 Children
	root.getRightChild().getLeftChild().getRightChild().getLeftChild().setLeftChild(chk.new BinTreeNode(9));	
	
	BinTreeNode check1=chk.new BinTreeNode(5);
	//Left L1 Children
	check1.setLeftChild(chk.new BinTreeNode(6));
	check1.setRightChild(chk.new BinTreeNode(78));
	check1.getLeftChild().setLeftChild(chk.new BinTreeNode(33));
	
	retVal=chk.isSubtree(root,check1);
	System.out.println("Is Check1 subtree of Orig tree: "+retVal+"\n\n");	
	
	BinTreeNode check2=chk.new BinTreeNode(33);
	retVal=chk.isSubtree(root,check2);
	System.out.println("Is Check2 subtree of Orig tree: "+retVal+"\n\n");	
	
	BinTreeNode check3=chk.new BinTreeNode(16);
	check3.setLeftChild(chk.new BinTreeNode(18));
	check3.getLeftChild().setLeftChild(chk.new BinTreeNode(9));
	retVal=chk.isSubtree(root,check3);
	System.out.println("Is Check3 subtree of Orig tree: "+retVal+"\n\n");	
	
	BinTreeNode check4=chk.new BinTreeNode(16);
	check4.setLeftChild(chk.new BinTreeNode(18));
	check4.setRightChild(chk.new BinTreeNode(28));
	check4.getLeftChild().setLeftChild(chk.new BinTreeNode(9));
	retVal=chk.isSubtree(root,check4);
	System.out.println("Is Check4 subtree of Orig tree: "+retVal+"\n\n");	
	
	BinTreeNode check5=chk.new BinTreeNode(4);
	retVal=chk.isSubtree(root,check5);
	System.out.println("Is Check5 subtree of Orig tree: "+retVal+"\n\n");
	
	BinTreeNode check6=chk.new BinTreeNode(4);
	check6.setLeftChild(chk.new BinTreeNode(5));
	retVal=chk.isSubtree(root,check6);
	System.out.println("Is Check5 subtree of Orig tree: "+retVal+"\n\n");
	
	}catch (Exception exception) {
	System.out.print("Exception: "+ exception);
	exception.printStackTrace();
	}
		
	}

public class BinTreeNode {
	private BinTreeNode leftNode=null;
	private BinTreeNode rightNode=null;
	private int nodeData=0;
	
	public BinTreeNode(int data) {
		nodeData=data;
	}	
	public BinTreeNode getLeftChild() {
		return leftNode;
	}
	public void setLeftChild(BinTreeNode leftNode) {
		this.leftNode = leftNode;
	}
	public BinTreeNode getRightChild() {
		return rightNode;
	}
	public void setRightChild(BinTreeNode rightNode) {
		this.rightNode = rightNode;
	}
	public int getNodeData() {
		return nodeData;
	}
	public void setNodeData(int nodeData) {
		this.nodeData = nodeData;
	}

}


}