Determine if a binary tree is subtree of another binary tree using pre-order and in-order strings

Question

I want to find out whether binary tree T2 is a subtree of of binary tree T1. I read that one could build string representations for T2 and T1 using pre-order and in-order traversals, and if T2 strings are substrings of T1 strings, T2 is a subtree of T1.

I am a bit confused by this method and not sure about its correctness.

From wiki: "A subtree of a tree T is a tree consisting of a node in T and all of its descendants in T."

In the following example:

T2:
  1
 / \
2   3

T1:
  1
 / \
2   3
     \
      4

If we build the strings for T2 and T1:

preorder T2: "1,2,3"
preorder T1: "1,2,3,4"
inorder T2: "2,1,3"
inorder T1: "2,1,3,4"

The T2 strings are substrings of T1, so using the substring matching method described above, we should conclude T2 is a subtree of T1.

However, T2 by definition shouldn't be a subtree of T1 since it doesn't have all the descendants of T1's root node.

There is a related discussion here, which seems to conclude the method is correct.

Am I missing something here?

Answer 1

Assuming you got this from the book "Cracking the Coding Interview", the author also mentions that to distinguish between nodes with the same values, one should also print out the null values.

This would also solve your problem with the definition of a subtree (which is correct as also described in the book)

preorder T2: "1, 2, null, null, 3, null, null" preorder T1: "1, 2, null, null, 3, null, 4, null, null" inorder T2: "null, 2, null, 1, null, 3, null" inorder T1: "null, 2, null, 1, null, 3, null, 4, null"

As you can see, T2 is not a subtree of T1

Answer 2

Very interesting question. You seem to be correct. I suppose the issue that you mention arises due to different definitions of subtree in math (graph theory) and computer science. In graph theory T2 is a proper subtree of T1.