Tree traversal.
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.
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.
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)))