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.


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. 


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

class Code{
    public class Node{
        int value;
        Node left, right;
        Node(int value){this.value = value;}
        Node(int value, Node left, Node right){
            this.value = value;
            this.left = left;
            this.right = right;
        public String toString(){
            return "Value: "+value;
        public boolean equals(Object o){
            return o.hashCode() == this.hashCode();

        public int hashCode() {
            return value;
    private void getIdenticals(Node node, Node B, List<Node> store){
        if(node==null) return;
        if(node.equals(B)) store.add(node);
        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;
            if(match(head.left, B.left) && match(head.right, B.right)) return true;
        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();
        System.out.println(tree.isSubtree(tree.A, tree.B));



No comments:

Post a Comment