Algorithm to determine if a tree is a subtree of another tree

Question

I am reading a hack coding interview, and I have a question about solving 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 he offers is to create a string representing the traversal in order and preorders, and check if the T2s is a preorder / ordinal traversal substring of a preliminary request / traversal of order T1.

What interests me is why do we need to compare both workarounds? And why exactly these two rounds, why not, for example, in the order and after the order. And basically, one round will not be enough? Say only a crawl or a preliminary crawl?

Answer 1

One workaround is not enough. Consider the graphs 1-> 2-> 3 and 2 <-1-> 3. If you start with node 1 and crawl, you encounter the nodes in the order 1, 2, 3. If you just create a row with a pre-order, then two give the same result: 1,2,3

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

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

So, the question that you need to answer yourself to any other pair that you want to look at will be: is there a tree that will give the same order for both walks? I'm going to leave this as something to think about and come back later to find out if you have it.

Answer 2

I think a preliminary walk with a sentinel to represent a null node is enough. we can use this approach to serialize / deserialize a binary tree. This means that this is a one-to-one mapping between a binary tree with pre-order + intentional representation.

After we get the rows for both the small tree and the large tree. then we do string matching using the kmp algorithm.

I know that people say that we should use both preorder and inorder (or postorder and inorder). but most of them simply follow what others say, and not think independently.