9
$\begingroup$

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:

enter image description here

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.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Can you define in-order traversal for a generic tree (not necessarily binary)? What would that mean? $\endgroup$
    – Leonid Shifrin
    Commented Mar 21, 2017 at 19:03
  • $\begingroup$ @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. $\endgroup$
    – Mr.Wizard
    Commented Mar 21, 2017 at 19:34
  • 2
    $\begingroup$ For the GIH branch, how does one decide which is left and which is right? $\endgroup$
    – wxffles
    Commented Mar 21, 2017 at 20:24
  • $\begingroup$ @wxffles It was a quick fix so I self-answered instead of deleting. $\endgroup$
    – Mr.Wizard
    Commented Mar 22, 2017 at 0:03
  • $\begingroup$ @Mr.Wizard, as left and right branches have been assigned an order, why can't 3 or more branches be similarly ordered? $\endgroup$
    – alancalvitti
    Commented Apr 11, 2018 at 17:04

1 Answer 1

Reset to default
7
$\begingroup$

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 *)
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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