Tree traversal.

Question

Write the shortest code that traverses a tree, breadth-first.

Input

any way you like

Output

a list of "names" of the nodes in correct order.

Answer 1

edit: Common Lisp (69 chars)

returns rather than prints the list and takes input as argument

(defun b(e)(apply #'nconc (mapcar #'car (cdr e))(mapcar #'b (cdr e))))

Format is the same as below except it requires a 'dummy' root node like so:

(root (a (b (1) (2)) (c (1) (2))))

Common Lisp: (95 chars)

This one reads and prints instead of using arg parsing

(labels((b(e)(format t "~{~A~%~}"(mapcar #'car (cdr e)))(mapcar #'b (cdr e))))(b`((),(read))))

input to stdin should be a lisp form s.t. a tree with root a and two children b and c, each of which have children 1 & 2 should be (a (b (1) (2)) (c (1) (2)))

or equivalently -

(a 
  (b 
    (1)
    (2))
  (c
    (1)
    (2)))

Answer 2

Bash: (3 chars)

cat

Using your "input any way you want", I'll take it as a list of nodes (one per line) in bredth first traversal order ;)

Edit: since i seem to need to defend the fact that this does in fact traverse, in bredth first order, a specific representation of a tree.

In this program trees are represented as a sequence of bytes, just as they are in any other language. It just so happens that using this representation of a tree, BFS is an extremely optimized operation - in-order iteration over those bytes. since the desired behaviour is outputting those bytes, cat does this in an efficient way.

Incidently, this exact representation is very commonly used to represent binary heaps, which are a type of tree.

Edit 2

For this to be a legitimate tree, the above code assumes a fixed number of children and a complete, balanced tree, if this is not the case then the following will work (still assumes binary tree, or at least fixed number of children):

Sed: (5 chars)

/^$/d

assuming the input is a line-based variant of the standard structure of a heap - i.e. root is line 0, its children are lines 1 & 2, 1's children are 3 and 4, 2's children are 5 & 6 and so on. blank lines represent missing children.

Answer 3

Haskell — 84 76 characters

data N a=N{v::a,c::[N a]}
b(N a b)=d[a]b
d r[]=r
d r n=d(r++(map v n))$n>>=c

In a more readable format:

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

bfs :: Node Int -> [Int]
bfs (Node a b) = bfs' [a] b
  where bfs' res [] = res
        bfs' res n = bfs' (res ++ (map value n)) $ concatMap children n

The code allows infinite number of child nodes (not just left and right).

Sample tree:

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

Sample run:

*Main> b sampleTree
[1,2,3,4,5,6,7,8,9,10,11,12]

Nodes are expanded in the order shown in Breadth-first search article on Wikipedia.

Answer 4

Not a serious answer, but the Golfscript version of tobyodavies' sed answer is only 4 chars

n%n*

you could argue that

n%

is also sufficient,as it returns the tree items as a list, however these are displayed mashed together on stdout.

n%p

displays the list representation of the tree items (looks like a Python or Ruby list)

Answer 5

Python - 59 chars

This one returns a generator, but modifies T, so you may want to pass in a copy

def f(T):
 t=iter(T)
 for i in t:yield i;T+=next(t)+next(t)

testing

              4
             / \
            /   \
           /     \
          2       9
         / \     / \
        1   3   6   10
               / \
              5   7
                   \
                    8

>>> T=[4,[2,[1,[],[]],[3,[],[]]],[9,[6,[5,[],[]],[7,[],[8,[],[]]]],[10,[],[]]]]
>>> f(T)
<generator object f at 0x87a31bc>
>>> list(_)
[4, 2, 9, 1, 3, 6, 10, 5, 7, 8]

Answer 6

Haskell: 63 characters

data N a=N{v::a,c::[N a]}
b n=d[n]
d[]=[]
d n=map v n++d(n>>=c)

This is really just a variation on @Yasir's solution, but that one isn't community wiki, and I couldn't edit it.

By just expanding the names, and replacing concatMap for >>=, the above golf'd code becomes perfectly reasonable Haskell:

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

breadthFirst t = step [t]
  where step [] = []
        step ts = map value ts ++ step (concatMap children ts)

The only possibly golf-like trick is using >>= for concatMap, though even that isn't really that uncommon in real code.