HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Is there a name for this tree traversal?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
thisnamefortheretreetraversal

Problem

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:

A
 / \
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?

Solution

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.

Context

StackExchange Computer Science Q#90397, answer score: 2

Revisions (0)

No revisions yet.