Tree traversal: Depth-first search Write the shortest code that traverses a tree, depth-first.

Input

Any programmatical structure found in your language of choice: lists, tuples, queues etc.

Output

A list of "names" of the nodes in correct order as shown in Depth-first search article at Wikipedia.
Haskell — 70 characters

data N a=N{v::a,c::[N a]}
d n=f[n][]
f(x:y)=f(c x++y).(++[v x])
f _=id


In a more readable format:

data Node a = Node {value::a, children::[Node a]}

dfs :: Node a -&gt; [a]
dfs node = dfs' [node] []
  where dfs' [] result = result
        dfs' (x:xs) result = dfs' (children x ++ xs) (result ++ [value x])


Sample tree:

sampleTree = 
    Node 1 [Node 2 [Node 3 [Node 4 [],
                            Node 5 []], 
                    Node 6 []],
            Node 7 [], 
            Node 8 [Node 9 [Node 10 [],
                            Node 11 []],
                    Node 12 []]]


Sample run:

*Main&gt; dfs sampleTree
[1,2,3,4,5,6,7,8,9,10,11,12]