# 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

1. Flatten your pattern into a breadth-first array of tuples including the node name, depth, and index, like:

(a,0,0), (b,1,0), (c,1,1), (d,2,0)...

2. Traverse (or flatten) your input tree in breadth-first order, ideally using the same method.
3. The n-th item in your pattern array will match the n-th item in the input tree, assuming there is one. You can use the depth and index values of each tuple to skip ahead until something matches.
There are really good breadth-first traversal code samples all over the place, it should be easy to find one in the language of your choice.

-