Algorithm to identify if tree is subtree of other tree

Question

I am reading cracking the coding interview, and I have a question on the solution of the following problem: You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.

The simple solution that it suggests is to create a string representing the in-order and pre-order traversals and check if T2s pre-order/in-order traversal is substring of T1's pre-order/in-order traversal.

What I wonder is why do we need to compare both traversals? And why exactly that two traversals, why not for example in-order and post-order. And mainly won't only one traversal be enough? Say only in-order or pre-order traversal?

Answer 1

One traversal isn't enough. Consider the graphs 1->2->3 and 2<-1->3. If you start with node 1 and do a traversal, you encounter the nodes in the order 1, 2, 3. If you simply create a string showing the pre-order the two give the same result: 1,2,3

On the other hand, if you use a post-order, then the two will give a different result. 3,2,1 and 2,3,1

I bet for any one ordering, you can find two different trees with the same result.

So the question you need to answer for yourself for any other pair you want to look at is: would there be a tree that would give the same order for both traversals? I'm going to leave that as something to think about and come back later to see if you've got it.