# 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. Feb 25, 2013 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. Feb 25, 2013 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. Feb 25, 2013 at 22:14
• I see what you mean. I thought he said `d` instead of `c`. Feb 25, 2013 at 23:05
• I'm pretty sure he meant d instead of c.
– psr
Feb 26, 2013 at 0:14