Interview Questions

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) {
this.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):
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);
}
nodes.push(root.data);
if (root && root.right) {
in_order(root.right, nodes);
}
return nodes;
}

// pre-order traversal in array format
function pre_order(root, nodes) {
nodes.push(root.data);
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)
nodes.append(root.data)
if root and root.right:
in_order(root.right, nodes)
return nodes

# pre-order traversal in array format
def pre_order(root, nodes):
nodes.append(root.data)
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.

## Sources

https://www.glassdoor.com/Interview/Given-two-binary-trees-T1-and-T2-Find-if-T2-is-a-sub-tree-of-T1-QTN_250138.htm
mrdaniel published this on 6/11/16 |
• +
• 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; ```
• +
• 2
• -
• I believe you can use in order traversal as well.
• +
• 2
• -
• ``` //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.