An interesting approach on checking if a tree is a sub tree of another | Hacker News Reader

An interesting approach on checking if a tree is a sub tree of another

mohit.athwani.net

20 pointsobjectivem5 comments

If you can spare some computation time when creating the trees you can simply generate recursive hashes (like git does), then you can immediately see if a given tree exists anywhere as a subtree of a larger tree in O(1). Of course you will pay for this with O(n) time complexity and storage for creating and storing the hashes.

Not really O(1), you still need to go through the big tree to find the node with teh deisred hash. You also have to check if the trees are truly identical to handle the case of hash collision.

The idea is that you create a hash map where the key is a tree hash and the value points to the tree in memory, so it should be O(1). Hash collision can of course happen but is extremely unlikely if you use a robust scheme like SHA256.

Uhh. Only checking for pre-order is incorrect. You need to check both in-order AND pre-order strings.

   2      1
  / \      \
 1   3      3

The pre-order strings match (213 & 13) but the second tree is not a subtree of the first.

The in-order strings (123 & 13) don't match.

What if the string representation of a node can look like a sequence of other nodes? Doesn't this approach need a node separator string that doesn't appear in the data?

Reply on news.ycombinator.com