Tree traversal. [closed]

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

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 2

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 3

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.

Answer 4

GolfScript, 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]