Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a tree:

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

And the pattern:

   / \
  y   z
 / \
q   p

As output I would like to have:

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


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

Is there any algorithm I could look at?

share|improve this question
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
up vote 1 down vote accepted

  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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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