# why Level does not sort output according to their levels

Consider this example:

Level[a + f[x, y^n], {0, Infinity}]

(*{a, x, y, n, y^n, f[x, y^n], a + f[x, y^n]}*)


Why the output is sorted in this way. why not following their levels? I was expecting to get:

(*{a + f[x, y^n], a, f[x, y^n], x, y^n, y, n}*)

• Details&Options: "Level traverses expressions in depth-first order, so that the subexpressions in the final list are ordered lexicographically by their indices.". So in your case use: Flatten[Table[Level[#, {i}], {i, 0, Depth[#]}]] & – Kuba Jul 28 '14 at 8:54
• @Kuba can you let me know how to get the indices of all Level output so that I can understand waht you mean by ordered lexicographically by their indices. – Algohi Jul 28 '14 at 10:18

As Kuba comments Level follows the standard expression traversal order:

Level traverses expressions in depth-first order, so that the subexpressions in the final list are ordered lexicographically by their indices.

This is actually a depth-first postorder traversal.
It is the normal order in which expressions are evaluated in Mathematica:

echo[x_] := (Print@x; x)

expr = a + f[x, y^n];

Map[echo, HoldForm @@ {expr}, {1, -1}]

ReleaseHold[%];

echo[echo[a] + echo[f[echo[x], echo[echo[y]^echo[n]]]]]


a
x
y
n
y^n
f[x,y^n]
a+f[x,y^n]

It is used by nearly all System traversal functions, e.g.:

Scan[Print, expr, {0, -1}]  (* same output as above; omitted *)

Cases[expr, _, {0, -1}]

expr ~Extract~ Position[expr, _, {0, -1}, Heads -> False]

{a, x, y, n, y^n, f[x, y^n], a + f[x, y^n]}

{a, x, y, n, y^n, f[x, y^n], a + f[x, y^n]}


A notable exception is ReplaceAll which uses a depth-first preorder traversal. See:

You are interested in a breadth-first traversal; see:

For an understanding of levels as used by Mathematica see the excellent illustrations in answer to:

### Solution to implied problem

Although I hope the information above including the linked Q&A's will give you the knowledge to solve the implied problem yourself here is my take on Kuba's code:

expr = a + f[x, y^n];

Array[expr ~Level~ {#} &, Depth @ expr, 0, Join]

{a + f[x, y^n], a, f[x, y^n], x, y^n, y, n}


And a solution using WReach's bf function from the link above:

Reap[Sow ~bf~ expr][[2, 1]]

{a + f[x, y^n], a, f[x, y^n], x, y^n, y, n}