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.

$\endgroup$
5
  • 1
    $\begingroup$ Can you define in-order traversal for a generic tree (not necessarily binary)? What would that mean? $\endgroup$ 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
    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
    Mar 21, 2017 at 20:24
  • $\begingroup$ @wxffles It was a quick fix so I self-answered instead of deleting. $\endgroup$
    – Mr.Wizard
    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$ Apr 11, 2018 at 17:04

1 Answer 1

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 *)
$\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.