## Thursday, January 1, 2015

### Checking if a given binary tree is a sub-tree of another binary tree.

Q. You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.

A tree T2 is a subtree of T1 if there exists a node n in T1 such that the subtree of n is identical to T2. That is, if you cut off the tree at node n, the two trees would be identical.

Algorithm:

1. Traverse T1, find nodes that match the root of T2.
2. For all the nodes that match, check if the trees with those roots are equivalent.

Source:

```import java.util.ArrayList;
import java.util.List;

class Code{
public class Node{
int value;
Node left, right;
Node(){}
Node(int value){this.value = value;}
Node(int value, Node left, Node right){
this.value = value;
this.left = left;
this.right = right;
}

@Override
public String toString(){
return "Value: "+value;
}

@Override
public boolean equals(Object o){
return o.hashCode() == this.hashCode();
}

@Override
public int hashCode() {
return value;
}
}

private void getIdenticals(Node node, Node B, List<Node> store){
if(node==null) return;
getIdenticals(node.left, B, store);
getIdenticals(node.right, B, store);
}

public boolean isSubtree(Node root, Node B){
if(root == null || B == null)return false;
List<Node> possibleNodes = new ArrayList<>();
getIdenticals(root, B, possibleNodes);
for(Node n:possibleNodes)
if(match(n, B))return true;
return false;
}

private boolean match(Node head, Node B){
if(head==null && B == null)return true;
if(head==null || B == null)return false;
}
return false;
}

Node root;
Node A, B;

public void buildCustomTree(){
A = root = new Node(5);
setChildren(root, 7, 6);
setChildren(root.left, 8, 10);
setChildren(root.left.right, 12, 13);
setChildren(root.left.right.left, 14, null);
setChildren(root.left.right.right, null, 15);
setChildren(root.left.right.right.right, 16, 17);
setChildren(root.left.right.right.right.left, null, 18);
setChildren(root.right, null, 11);

B = new Node(13);
setChildren(B, null, 15);
setChildren(B.right, 16, 17);
setChildren(B.right.left, null, 18);
}

private void setChildren(Node node, Integer left, Integer right){
if(left!=null)node.left = new Node(left);
if(right!=null)node.right = new Node(right);
}

public static void main(String[] args){
Code tree = new Code();
tree.buildCustomTree();
System.out.println(tree.isSubtree(tree.A, tree.B));
}
}```

Output:

true