[ninetyninenine]

Am I mistaken? Is what you say even possible?

Given two graphs one is a tree you cannot determine if the tree is a subgraph of the other graph in one walk through?

It’s only possible if you’re given additional information? Like a starting node to search from? I’m genuinely confused?

[jcynix]

Take a look at Carl Hewitt's Same-Fringe solution, which flattens structures concurrently and compares the final (aka leave) nodes:

http://www.nsl.com/papers/samefringe.htm

If you flatten both of your trees/graphs and regard the output as strings of nodes, you reduce your task to a substring search.

Now if you want to verify if the structures and not just the leave nodes are identical, you might be able to encode structure information into you strings.

[ninetyninenine]

Thanks. Good solution.

I was thinking in terms of finding all subgraph isomorphisms. But this definitely is O(N) if all you need is one solution.

But then I thought about it even further and this reduces to sliding window problem. In this case you still need to travel to each node in the window to see if there’s a match.

So it cannot be that you traverse each node once. Not if you want to find all possible subgraph isomorphisms.

Imagine a string that is a fractal of substrings:

     rrrrrrrrrrrrrrrrrrrrrrrrrrrr

And the other one:

     rrrrrrr

Right? The sliding window for rrrrrrr will be 7 in length and you need to traverse that entire window every time you move it. So by that fact alone every node is traversed at least 7 times.

[bironran]

I oversimplified. See https://news.ycombinator.com/item?id=44390701