Finding subtree in a tree

Question

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, 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. — Karl Bielefeldt, 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. — FrustratedWithFormsDesigner, Feb 25, 2013 at 22:14

jzx · Accepted Answer · 2013-02-25 22:06:02Z

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)...
Traverse (or flatten) your input tree in breadth-first order, ideally using the same method.
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.

1 Answer 1