This came when I was looking at block scoping in compiler design.

{   A   { B }   { C {D} {E} }   }

For the above pseudo code, the order in which the scope varies as we scan left to right is A B A C D C E C A, where A to E represent scopes.

A parse tree can be constructed for the above pseudo code:

 / \
B   C
   / \
  D   E

Is their a term for such a traversal order, which for the above tree is A B A C D C E C A?

  • 2
    $\begingroup$ DFS? $\endgroup$ – xskxzr Apr 8 '18 at 13:43
  • $\begingroup$ Pre-order traversal? $\endgroup$ – Luke Mathieson Apr 8 '18 at 13:50
  • $\begingroup$ @LukeMathieson not pre-order. Main difference is, what we normally call traversal do not represent a tree vertex more than once within the output string. $\endgroup$ – Apiwat Chantawibul Apr 8 '18 at 14:05
  • $\begingroup$ @billiska: but nothing stops you from doing more than one action during a DFS. In this case, there are pre-, in- and post-order actions. $\endgroup$ – rici Apr 8 '18 at 15:34

For a binary tree that is triple order; each node is visited three times in pre- in- and post-order. Knuth cites it from a paper by Lindstrom and Dwyer; it can be done without a stack by updating the tree in place.

  • $\begingroup$ I think "triple order" would be more applicable to a binary tree than an n-ary tree. $\endgroup$ – Fauzan Apr 12 '18 at 1:41
  • $\begingroup$ Correct, I had assumed it was binary. I'm updating the answer to clarify. $\endgroup$ – KWillets Apr 12 '18 at 16:27
  • $\begingroup$ Interestingly, I think the stackless algorithm can work on an n-ary tree; it works by shifting the child list left and appending a back-link to the parent, so n children is OK. But that's a different question. $\endgroup$ – KWillets Apr 12 '18 at 16:32

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.