# Tree traversal. [closed]

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

any way you like

### Output

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

• What do you mean by correct order? Ascending? Mar 14, 2014 at 13:17
• @sindikat, the order traversed. Mar 14, 2014 at 14:11

# 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.

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

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.

• 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! Feb 18, 2011 at 9:17

# 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)

(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)))

• Funny, but cryptic. Even Scheme experience doesn't help much. :-) Jan 28, 2011 at 15:01
• 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 ;) Jan 28, 2011 at 15:05
• 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... Jan 28, 2011 at 15:27
• Aah, thanks, I'll look into that. Jan 28, 2011 at 15:35

# 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)

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