How to check if a non binary tree is a subtree of another

Question

I'm working with trees and i need to know how to check if if a non binary tree is a subtree of another.

These trees could have n nodes and n levels, and the children's order is not important. I just to know if the tree is a subtree of another

The problem for me is how to do a recursion and compare both tree at the same time with a recursion.

for that i create an exemple to demonstrate what i want to do.

I know the roots of both tree and i;m trying to do that in ruby on rails, but for know i justa want to know a pseudo code or the logic.

Someone can help me?

Thanks

Answer 1

I would try to use ideas from hash tree or Merkle Tree:

a hash tree or Merkle tree is a tree in which every non-leaf node is labelled with the hash of the labels of its children nodes. Hash trees are useful because they allow efficient and secure verification of the contents of large data structures.

See also Hashing a Tree Structure