Interview Questions

  • View all algorithm tutorials
  • blank
  • Determine if binary tree is a subtree of a larger binary tree
    In a previous algorithm tutorial we discussed how to traverse a tree using different algorithms. Now we'll solve a popular tree algorithm question of determining if a binary tree is a subtree within a larger tree. In the picture below, you can see that the tree on the left is contained within the tree on the right, underneath the gray node with a value of 10. We can assume the tree is properly constructed via the following code which sets up nodes and links them to their proper child nodes:
    function Node(data) { = data;
      this.left = null;
      this.right = null;
    // left tree
    var root = new Node(10);
    var n1 = new Node(4);
    var n2 = new Node(6);
    var n3 = new Node(30);
    // setup children
    n1.right = n3;
    root.left = n1;
    root.right = n2;
    // right tree
    var root_r = new Node(26);
    var n1_r = new Node(10);
    var n2_r = new Node(3);
    var n3_r = new Node(4);
    var n4_r = new Node(6);
    var n5_r = new Node(3);
    var n6_r = new Node(30);
    // setup children
    n3_r.right = n6_r;
    n1_r.left = n3_r;
    n1_r.right = n4_r;
    n2_r.right = n5_r;
    root_r.left = n1_r;
    root_r.right = n2_r;
    class Node:
      def __init__(self, data): = str(data)
        self.left = None
        self.right = None
    # left tree
    root = Node(10)
    n1 = Node(4)
    n2 = Node(6)
    n3 = Node(30)
    # setup children
    n1.right = n3
    root.left = n1
    root.right = n2
    # right tree
    root_r = Node(26)
    n1_r = Node(10)
    n2_r = Node(3)
    n3_r = Node(4)
    n4_r = Node(6)
    n5_r = Node(3)
    n6_r = Node(30)
    # setup children
    n3_r.right = n6_r
    n1_r.left = n3_r
    n1_r.right = n4_r
    n2_r.right = n5_r
    root_r.left = n1_r
    root_r.right = n2_r

    The algorithm

    To solve this problem in linear time, we will first produce the in-order and pre-order arrays for both trees, and then we will determine if the in-order and pre-order arrays of the first tree are contained somewhere within the arrays of the second tree. The reason the algorithm above works is because to uniquely identify a binary tree, an in-order and pre-order traversal is needed. So, because we are getting these traversal arrays for both trees, the last step will simply be to check if the smaller tree is contained in the larger one by checking their traversal arrays.
    // in-order traversal in array format
    function in_order(root, nodes) {
        if (root && root.left) {
            in_order(root.left, nodes);   
        if (root && root.right) {
            in_order(root.right, nodes);  
        return nodes;
    // pre-order traversal in array format
    function pre_order(root, nodes) {
        if (root && root.left) {
            pre_order(root.left, nodes);   
        if (root && root.right) {
            pre_order(root.right, nodes);  
        return nodes;
    // function that takes two root nodes and determines if
    // the first tree is a subtree of the second tree
    function is_subtree(root, root_r) {  
        // the variables below will hold the values:
        // 4-30-10-6 
        // 4-30-10-6-26-3-3
        var inord1 = in_order(root, []).join('-'); 
        var inord2 = in_order(root_r, []).join('-');
        // 10-4-30-6
        // 26-10-4-30-6-3-3
        var preord1 = pre_order(root, []).join('-');
        var preord2 = pre_order(root_r, []).join('-');
        // check if the left tree is contained with the right tree
        return inord2.indexOf(inord1) !== -1 && preord2.indexOf(preord1) !== -1;
    is_subtree(root, root_r); // => true
    # in-order traversal in array format
    def in_order(root, nodes):
        if root and root.left:
            in_order(root.left, nodes)
        if root and root.right:
            in_order(root.right, nodes)
        return nodes
    # pre-order traversal in array format
    def pre_order(root, nodes):
        if root and root.left:
            pre_order(root.left, nodes)
        if root and root.right:
            pre_order(root.right, nodes)
        return nodes
    # function that takes two root nodes and determines if
    # the first tree is a subtree of the second tree
    def is_subtree(root, root_r):
        # the variables below will hold the values:
        # 4-30-10-6 
        # 4-30-10-6-26-3-3
        inord1 = '-'.join(in_order(root, []))
        inord2 = '-'.join(in_order(root_r, []))
        # 10-4-30-6
        # 26-10-4-30-6-3-3
        preord1 = '-'.join(pre_order(root, []))
        preord2 = '-'.join(pre_order(root_r, []))
        # check if the left tree is contained with the right tree
        return inord1 in inord2 and preord1 in preord2
    print is_subtree(root, root_r) # => True

    Running time

    The running time of this algorithm is linear, or O(n), because for both trees, it only traverses them each exactly two times which is constant. Then to check if a substring is contained within another string, a linear time algorithm can be used for this as well, such as the KMP algorithm or others.

    mrdaniel published this on 6/11/16 | tree, traversal, subtree
  • +
  • 14
  • -
  • This algorithm is incorrect. It can produce false positives if the `inord` match and the `preord` match occur in unrelated parts of the original tree. // smaller tree // var root = new Node(1); var n2 = new Node(2); var n3 = new Node(3); // root.left = n2; root.right = n3; // larger tree var root_r = new Node(0); var n_l1 = new Node(1); var n_l2 = new Node(2); var n_l3 = new Node(3); var n_r1 = new Node(1); var n_r2 = new Node(2); var n_r3 = new Node(3); // root_r.left = n_l1; n_l1.left = n_l2; n_l2.left = n_l3 root_r.right = n_r1; n_r1.right = n_r2; n_r2.right = n_r3;
  • +
  • 3
  • -
  • I believe you can use in order traversal as well.
  • +
  • 3
  • -
  • //First find position of T2 in T1 Node findPosition(T1, T2){ if(T1==null) return null; if(T1==T2){ // starting node of sub child found return T1; } Node left=findPosition(T1->left, T2); if(left!=null) return left; return findPosition(T1->right,T2); } //compare the two trees compareTree(T1,T2){ if(T1==null && T2==null) return true; if(T1==null||T2==null) return false; return (T1==T2)&&compareTree(T1->left,T2->left)&&(T1->right&&T2->right); } //Method which checks for subtree. boolean hasSubTree(T1,T2){ // Checks if there is a sub tree in the parent tree starting with the root node of child tree. Node pos=findPosition(T1,T2); if(pos==null){ return false; } return compareTree(pos,T2); }
  • +
  • 1
  • -
  • Convert trees to a unique string 'nodd(left,right)' e.g. '26(10(4(,30),6),3(,3))' and '10(4(,30),6)' and look for a substring in fiirst tree in second tree. Complexity is O(n) wher n is number of nodes in larger tree class node: def __init__(self,value): self.value=value self.rightChild=None self.leftChild=None def addLeftChild(self,node_c): self.leftChild=node_c def addrightChild(self,node_c): self.rightChild=node_c def tree_to_string(self): if self.leftChild==None and self.rightChild==None: return str(self.value) if self.leftChild==None and self.rightChild!=None: return str(self.value)+'('+','+self.rightChild.tree_to_string()+')' if self.leftChild!=None and self.rightChild==None: return str(self.value)+'('+self.leftChild.tree_to_string()+','+')' return str(self.value)+'('+self.leftChild.tree_to_string()+','+self.rightChild.tree_to_string()+')' def checkSubtree(tree1,tree2): str1=tree1.tree_to_string() str2=tree2.tree_to_string() print(str1,str2) if str2 in str1: return True else: return False if __name__ == '__main__': tree1=node(26) tree1.addrightChild(node(3)) tree1.addLeftChild(node(10)) tree1.rightChild.addrightChild(node(3)) tree1.leftChild.addrightChild(node(6)) tree1.leftChild.addLeftChild(node(4)) tree1.leftChild.leftChild.addrightChild(node(30)) tree2=node(10) tree2.addrightChild(node(6)) tree2.addLeftChild(node(4)) tree2.leftChild.addrightChild(node(30)) isSub=checkSubtree(tree1,tree2) print(isSub)
  • +
  • 0
  • -
  • Is it possible to use in-order and post-order travsersal to check if binary tree is a subtree of a larger binary tree?
  • +
  • 0
  • -
  • Let's modify @mhelvens 's right tree, and the false positive example is: // larger tree root_r.left = n_l1; n_l1.left = n_l2; n_l2.left = n_l3 root_r.right = n_r2; n_r1.right = n_r3; n_r3.left = n_r1;
  • +
  • -1
  • -
  • @mhelvens, The example you provided produces the following traversal arrays on the trees: inorder: [2, 1, 3] [3, 2, 1, 0, 1, 2, 3] preorder: [1, 2, 3] [0, 1, 2, 3, 1, 2, 3] You can see that in the preorder traversal the smaller array does in fact exist within the larger array, but for the inorder arrays, that is not the case. [2, 1, 3] is not contained in [3, 2, 1, 0, 1, 2, 3]. So this wouldn't produce a false positive because the is_subtree function will return false.
    Log in to submit a comment.