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


any way you like


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

  • \$\begingroup\$ What do you mean by correct order? Ascending? \$\endgroup\$ Commented Mar 14, 2014 at 13:17
  • \$\begingroup\$ @sindikat, the order traversed. \$\endgroup\$
    – Eelvex
    Commented Mar 14, 2014 at 14:11

5 Answers 5


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

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


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 -

  • \$\begingroup\$ Funny, but cryptic. Even Scheme experience doesn't help much. :-) \$\endgroup\$ Commented Jan 28, 2011 at 15:01
  • \$\begingroup\$ format is a language unto itself ;) and scheme doesn't have an equivalent. if you add spaces/newlines in sensible places and read gigamonkeys.com/book/a-few-format-recipes.html it should become clearer ;) \$\endgroup\$ Commented Jan 28, 2011 at 15:05
  • \$\begingroup\$ In short there is a function b that prints all of the immediate children one per line, then recurses on all of the children. (note it does not print itself). when b is first called it is given a fake tree with only one child such that the problem of not printing itself doesn't occur... \$\endgroup\$ Commented Jan 28, 2011 at 15:27
  • \$\begingroup\$ Aah, thanks, I'll look into that. \$\endgroup\$ Commented Jan 28, 2011 at 15:35

Haskell: 63 characters

data N a=N{v::a,c::[N a]}
b n=d[n]
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.

  • 1
    \$\begingroup\$ Wow, Haskell beats all other languages here. Haven't thought of shortening the code in that way; maybe I am just used to program in terms of Tail recursion. I think I should also note that both solutions allow infinite number of child nodes, and are type-safe, leveraging Type polymorphism unobtrusively. People, [learn,use,enjoy] Haskell! \$\endgroup\$ Commented Feb 18, 2011 at 9:17

GolfScript, 4

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


you could argue that


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


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


Python - 59 chars

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

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


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

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.