5
\$\begingroup\$

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.

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

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.

\$\endgroup\$
0
4
\$\begingroup\$

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.

\$\endgroup\$
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\$
    – YasirA
    Feb 18 '11 at 9:17
3
\$\begingroup\$

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)))
\$\endgroup\$
4
  • \$\begingroup\$ Funny, but cryptic. Even Scheme experience doesn't help much. :-) \$\endgroup\$
    – YasirA
    Jan 28 '11 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\$ Jan 28 '11 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\$ Jan 28 '11 at 15:27
  • \$\begingroup\$ Aah, thanks, I'll look into that. \$\endgroup\$
    – YasirA
    Jan 28 '11 at 15:35
2
+25
\$\begingroup\$

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)

\$\endgroup\$
1
\$\begingroup\$

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]
\$\endgroup\$
0

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