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

To complement my earlier questions:

I would now like to ask: how to perform a depth-first in-order traversal?

Wikipedia gives this illustration of the depth-first in-order traversal: The output is A, B, C, D, E, F, G, H, I.

I believe this traversal applies only to binary trees.

Here is an expression to experiment with, using Null for missing leaves.

tree = "F"["B"["A", "D"["C", "E"]], "G"[Null, "I"["H", Null]]];


I am interested in efficiency and elegance.

• Can you define in-order traversal for a generic tree (not necessarily binary)? What would that mean? – Leonid Shifrin Mar 21 '17 at 19:03
• @LeonidShifrin Good question. I cannot. I found the example in isolation interesting and wondered if there were already Mathematica functions that implement this, or other standard methods. The Wikipedia description applies to a binary tree, and I don't think this generalizes to an arbitrary number of leaves, as it visits the root node between left and right branches. – Mr.Wizard Mar 21 '17 at 19:34
• For the GIH branch, how does one decide which is left and which is right? – wxffles Mar 21 '17 at 20:24
• @wxffles It was a quick fix so I self-answered instead of deleting. – Mr.Wizard Mar 22 '17 at 0:03
• @Mr.Wizard, as left and right branches have been assigned an order, why can't 3 or more branches be similarly ordered? – alancalvitti Apr 11 '18 at 17:04

## Recursion

tree = "F"["B"["A", "D"["C", "E"]], "G"[Null, "I"["H", Null]]];

dfio[f_][Null | a_~r_~b_] := Scan[dfio[f], {a, r, b}]
dfio[f_][x_] := f[x]

dfio[Print][tree]


A

B

C

D

E

F

G

H

I

## Stack

Daniel showed how to manually manage a stack. Applying his method to this traversal:

dfioStack[f_, expr_] :=
Module[ {stack = {expr, {}}, el = expr},
While[ stack =!= {},
{el, stack} = stack;
If[ Length@el === 2,
Do[ stack = {el[[j]], stack}, {j, {2, 0, 1}}],
If[ el =!= Null, f @ el]
]
]
]

dfioStack[Print, tree]  (* same output as above *)