# How to perform a depth-first preorder traversal of an expression?

Mathematica provides functions that perform a depth-first postorder traversal, or which use such a traversal, including: Scan, Count, Cases, Replace, and Position. It is also the standard evaluation order therefore functions Mapped (Map, MapAll) will evaluate in a depth-first-postorder.

It is quite direct to do this:

expr = {{1, {2, 3}}, {4, 5}};

Scan[Print, expr, {0, -1}]


1

2

3

{2,3}

{1,{2,3}}

4

5

{4,5}

{{1,{2,3}},{4,5}}

It is not as obvious how to do a depth-first preorder scan. (Simply storing then reordering the output is not adequate as it doesn't change the order in which expressions are visited.)

Scan has the property that it does not build an output expression the way that e.g. Map does, and conserves memory.

How can one do a Scan-type operation in depth-first preorder?

Related:

• Related topic: I have implemented a special version of Cases which performs the depth-first preorder traversal (perhaps not optimally). In that case, this was important to avoid unpacking during the traversal performed by Cases. – Leonid Shifrin Aug 8 '12 at 20:52

I am aware of two general methods.

## ReplaceAll

The only general purpose function I am aware of that visits depth-first preorder is ReplaceAll. One can "scan" a given function such as Print as a side-effect by using either PatternTest or Condition, both of which only match if the return is explicitly True.

{{1, {2, 3}}, {4, 5}} /. _?Print -> Null;


{{1,{2,3}},{4,5}}
List
{1,{2,3}}
List
1
{2,3}
List
2
3
{4,5}
List
4
5

List is printed because ReplaceAll includes Heads whereas Scan by default does not.

We cannot use the level specification of Span but we can use patterns. For example:

{{1, {2, 3}}, {4, 5}} /. {_, _} ? Print -> Null;


{{1,{2,3}},{4,5}}
{1,{2,3}}
{2,3}
{4,5}

## Recursive function

This can be done using a recursive function, the purest form of which is:

(Print@#; #0 ~Scan~ #)& @ {{1, {2, 3}}, {4, 5}}


{{1,{2,3}},{4,5}}
{1,{2,3}}
1
{2,3}
2
3
{4,5}
4
5

Though not as fast as ReplaceAll this method can be extended more generally, for example to accept a level specification:

preorderScan[f_, expr_, {L1_, L2_}] :=
Module[{rec},
rec[n_][ex_] := (If[n >= L1, f@ex]; rec[n + 1] ~Scan~ ex);
rec[n_ /; n > L2][_] = Null;
rec[expr]
]

preorderScan[Print, {{1, {2, 3}}, {4, 5}}, {1, 2}]


{1,{2,3}}
1
{2,3}
{4,5}
4
5

(The function above is an illustration and not intended for reuse. It does not accept all forms of the standard levelspec and it makes no attempt to hold expressions unevaluated. If requested I can post a more lengthy version that does both.)

Here is a version that uses an explicit stack to avoid recursion.

depthFirstPreorder[expr_] := Module[
{stack = {expr, {}}, el = expr},
Reap[
While[stack =!= {},
{el, stack} = stack;
Sow[el];
If[Not[AtomQ[el]],
Do[stack = {el[[j]], stack}, {j, Length[el], 1, -1}]];
];
][[2, 1]]
]


The customary example:

expr = {{1, {2, 3}}, {4, 5}};

depthFirstPreorder[expr]

(* Out= {{{1, {2, 3}}, {4, 5}}, {1, {2, 3}}, 1, {2, 3}, 2, 3, {4,
5}, 4, 5} *)

• Daniel, I see that this is Reaping expressions; unlike Scan this is building an output expression, right? Is Sow simply an example function to "scan" over the expression? What are the tradeoffs of this method compared to recursion? – Mr.Wizard Aug 9 '12 at 4:39
• Yes, it builds an output expression. Sow is not an example function but rather is used in a necessary way. One could easily provide for a function to apply to subexpressions, though I did not. Main advantage is for deeply nested expressions because it will not blow up the program's subroutine stack. – Daniel Lichtblau Aug 9 '12 at 4:42

Don't know where this should fit. Playing around, this could be a more general approach to the traversal problem. It's probably not best for those traversals that can be done in other ways. Specifically, it has to create the list of indices all at once so it's not memory efficient as Scan

Module[{tag},
generalScan[fun_, expr_, sortingFun_: RandomSample] :=
Extract[Unevaluated@expr, If[# === {}, fun[expr]]; #, fun] &~Scan~
sortingFun[
Reap[MapIndexed[tag, Hold[expr], Infinity, Heads -> True] /.
tag[_, {1, in___}] /; Sow[{in}, tag] :> Null, tag][[-1, 1]]]]


This takes a third argument that makes you sort the list of indices to traverse. Defaults to RandomSample (hihihi)

expr = {{{1, {2}}}, {3, {4}}};

(* Random *)
generalScan[Print, expr]

generalScan[Print, expr, Sort]

generalScan[Print, expr, SortBy[#, Minus] &]

(* Depth-first preorder *)


...

It could be used for other purposes such as traversing a part of a tree. This would only traverse the leftmost branch

generalScan[Print, expr, Cases[#, {1 ..}] &]


TreeForm lays the expression tree out in a depth-first preorder traversal fashion. So observing that using VertexLabeling -> Tooltip gives you the expression at that level, we can redefine Tooltip using the Villegas–Gayley trick to print out the expressions as TreeForm lays out the tree. Replace Print with any desired function.

Unprotect@Tooltip;
Tooltip[expr_, label_] /; ! TrueQ[$insideTooltip] := Block[{$insideTooltip = True},
If[HoldPattern@label =!=
HoldPattern@NetworkGraphPlotDumpPrivatetp\$_, Print[label]];
Tooltip[expr, label]
]
Protect[Tooltip];
TreeForm[{{1, {2, 3}}, {4, 5}}, VertexLabeling -> Tooltip]

(*
{{1,{2,3}},{4,5}}
{1,{2,3}}
1
{2,3}
2
3
{4,5}
4
5
*)

• While clever, I wouldn't expect this to maintain the memory conserving performance of Scan, which is a fairly significant component of my question. – Mr.Wizard Aug 9 '12 at 3:22

My answer to the breadth first scan question (convert your expression to a Graph and do a BreadthFirstScan) can also be used for the depth first scan (if you have MMA v8). You only need to replace BreadthFirstScan by DepthFirstScan`. The latter is apparently (and luckily in this case) of the pre-order type.

For the code I refer to the answer referenced above. The visualization of the result is as follows: 