3

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?

6
  • 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
  • 2
    @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
  • 2
    @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

1 Answer 1

2

  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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.