Tree traversal: Depth-first search

Question

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.

Answer 1

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 -> [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> dfs sampleTree
[1,2,3,4,5,6,7,8,9,10,11,12]

Answer 2

Perl, 34

Perl 5.10 or later, run with perl -E'code here':

sub f{ref()?f($_):say for@{$_[0]}}

For example, running f [1,[2,[3,[4],[5]],[6]],[7],[8,[9,[10],[11]],[12]]] produces:

1
2
3
4
5
6
7
8
9
10
11
12

Answer 3

Haskell, 35 bytes

data D a=T[D a]a
d(T l n)=n:(d=<<l)

Try it online!

data D a=T[D a]a defines a labelled tree data structure. Constructor T takes a list of sub-trees and same value of an arbitrary type a (which however must be consistent throughout each tree).

Here is an example of a tree labelled with integers and the way this tree can be defined using the data structure:

   4
 / | \
1  5  2
  / \
 3   0

tree = T[T[]1, T[T[]3, T[]0]5, T[]2]4

The function d takes such a tree and returns a list of the tree's labels in depth-first order: Calling d tree yields [4,1,5,3,0,2].

Answer 4

PHP - 57 characters

<?function s($t){echo$t[0].'
';for(;$T=next($t);s($T));}

Test:

s(json_decode('[1,[2,[3,[4],[5]],[6]],[7],[8,[9,[10],[11]],[12]]]'));

Output:

1
2
3
4
5
6
7
8
9
10
11
12

Answer 5

Ruby - 37 35 31 25 characters

s=->t{p t.shift;t.map &s}

Test:

s[[1,[2,[3,[4],[5]],[6]],[7],[8,[9,[10],[11]],[12]]]]