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.

You need to be a premium member to see the rest of this question and code.

With our large collection of challengs, tutorials, and solutions, we make it easy for you to become a better coder, prepare for interviews, and learn new skills from more experienced coders.

- 200+ Coding Challenges
- Mock Interview Questions
- 500,000+ Code Solutions
- Algorithm Tutorials
- Interview Prep Courses

mrdaniel
published this on 6/11/16 **|**

0

@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.

mrdaniel

commented on 08/06/17

0

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;

mhelvens

commented on 06/24/17

Login to submit a comment