# Finding subtree in a tree

I have a tree:

``````    a
/ \
b   c
/ \
d   f
/ \
g   h
``````

And the pattern:

``````    x
/ \
y   z
/ \
q   p
``````

As output I would like to have:

``````x: a
y: b
z: c
q: d
p: f
``````

and

``````x: b
y: f
z: c
q: g
p: h
``````

Is there any algorithm I could look at?

-
your first pattern could be done with an easy breadth-first traversal (and stop after n nodes, where n = 5). The second pattern is a little weird to me because you process node f before c and g and h. – FrustratedWithFormsDesigner Feb 25 '13 at 21:57
@Frustrated, the second example makes sense if you assume that the order of children doesn't matter, which is a valid assumption for some trees. – Karl Bielefeldt Feb 25 '13 at 22:11
@KarlBielefeldt: I suppose... what threw me off is that c is a sibling of b but it is processed after b 's child is procesed, and before b 's grandchildren. – FrustratedWithFormsDesigner Feb 25 '13 at 22:14
I see what you mean. I thought he said `d` instead of `c`. – Karl Bielefeldt Feb 25 '13 at 23:05
I'm pretty sure he meant d instead of c. – psr Feb 26 '13 at 0:14