Check if a binary tree is sub-tree of another binary tree in time O(n)

Given two binary trees t1 and t2, check if tree t2 is sub-tree of tree t1. A sub-tree of tree T1 is a tree T2 having any one of the nodes 'n' and all the descendants of node 'n'.

In the following example, the middle tree - 'Tree_1' is sub-tree of leftmost tree - 'Tree_0'. Note that the rightmost tree - 'Tree_2' is not a sub-tree of 'Tree_0' because of the absence of node 8.


Video coming soon!



Subscribe for more updates


Algorithm/Insights

The algorithm is based on a simple idea that any binary tree could be uniquely represented by using in-order and pre-order traversal.

To check if tree 'smallTree' is sub-tree of tree 'bigTree', the steps of the algorithm are as following -
1. Find inorder traversals of 'smallTree' and 'bigTree'. Store them is string inorderForSmallTree and inorderForBigTree respectively.
2. Find preorder traversals of 'smallTree' and 'bigTree'. Store them is string preorderForSmallTree and preorderForBigTree respectively.
3. For 'smallTree' to be a sub-tree 'bigTree', string 'inorderForSmallTree' should be a substring of string 'inorderForBigTree' and string 'preorderForSmallTree' should be a substring of string 'preorderForBigTree'.

We could have also used post-order traversal string instead of pre-order traversal string in this algorithm.
Please checkout function checkIfSubtree(TreeNode bigTree, TreeNode smallTree) in code snippet for implementation details.

The time complexity of this algorithm is O(n) since traversal string could be formed in O(n) time and using KMP algorithm substring check could also be done in O(n) time; though for simplicty in the implementation we have used in-built java string API for substring check.

Space complexity for this approach is O(n) for storing traversal strings.


Algorithm Visualization




Code Snippet

			
package com.ideserve.questions.nilesh;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * Check if tree 't2' is sub-tree of tree 't1'
 * @author Nilesh
 */
public class CheckIfSubtree {

    class TreeNode
    {
        TreeNode left;
        TreeNode right;
        char key;
    
        public TreeNode(char key)
        {
            this.key = key;
        }
    }
    
    TreeNode root;

    /*
                            0
                      1             2
                  3      4       5  
                    6              7
                      8
    */

    private TreeNode createBigTree()
    {
        TreeNode n0 = new TreeNode('0');
        TreeNode n1   = new TreeNode('1');
        TreeNode n2   = new TreeNode('2');
        TreeNode n3   = new TreeNode('3');
        TreeNode n4   = new TreeNode('4');
        TreeNode n5   = new TreeNode('5');
        TreeNode n6   = new TreeNode('6');
        TreeNode n7   = new TreeNode('7');
        TreeNode n8   = new TreeNode('8');
        
        n0.left  = n1;
        n0.right = n2;
        
        n1.left  = n3;
        n1.right = n4;
        
        n2.left  = n5;
        
        n3.right = n6;
        
        n5.right = n7;
        
        n6.right = n8;
        
        root = n0;
        return n0;
    }


    /*
                      1             
                  3      4         
                    6              
                      8
    */
    private TreeNode createSmallTree()
    {
        TreeNode n1   = new TreeNode('1');
        TreeNode n3   = new TreeNode('3');
        TreeNode n4   = new TreeNode('4');
        TreeNode n6   = new TreeNode('6');
        TreeNode n8   = new TreeNode('8');
        
        n1.left  = n3;
        n1.right = n4;
        
        n3.right = n6;
        
        n6.right = n8;
        
        root = n1;
        return n1;
    }
    
    private void fillUpPreorderString(String[] traversalString, TreeNode node)
    {
        if (node == null)
        {
            return;
        }

        traversalString[0] += node.key;
        fillUpPreorderString(traversalString, node.left);
        fillUpPreorderString(traversalString, node.right);
    }

    
    private void fillUpInorderString(String[] traversalString, TreeNode node)
    {
        if (node == null)
        {
            return;
        }
        
        fillUpInorderString(traversalString, node.left);
        traversalString[0] += node.key;
        fillUpInorderString(traversalString, node.right);
    }
    
    
    public boolean checkIfSubtree(TreeNode bigTree, TreeNode smallTree)
    {
        String[] inorderForBigTree = {""};
        String[] inorderForSmallTree = {""};
        
        fillUpInorderString(inorderForBigTree, bigTree);
        fillUpInorderString(inorderForSmallTree, smallTree);
        
        if (inorderForBigTree[0].contains(inorderForSmallTree[0]))
        {
            String[] preorderForBigTree = {""};
            String[] preorderForSmallTree = {""};

            fillUpPreorderString(preorderForBigTree, bigTree);
            fillUpPreorderString(preorderForSmallTree, smallTree);

            return preorderForBigTree[0].contains(preorderForSmallTree[0]);
        }
        
        return false;
    }

    
    public static void main(String[] args) 
    {
        /*
                                0
                          1             2
                      3      4       5  
                        6              7
                          8
        */
        CheckIfSubtree bigTree = new CheckIfSubtree();
        bigTree.createBigTree();


        /*
                          1    
                      3      4 
                        6      
                          8
        */
        CheckIfSubtree smallTree = new CheckIfSubtree();
        smallTree.createSmallTree();
        
        System.out.println("If small tree is sub-tree of big tree: " + bigTree.checkIfSubtree(bigTree.root, smallTree.root));
    }
}
		

Order of the Algorithm

Time Complexity is O(n)
Space Complexity is O(n)


Contribution

  • Sincere thanks from IDeserve community to Nilesh More for compiling current post.


    Nilesh More