6
\$\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\$ – Mirzhan Irkegulov Mar 14 '14 at 13:17
  • \$\begingroup\$ @sindikat, the order traversed. \$\endgroup\$ – Eelvex Mar 14 '14 at 14:11
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\$ – tobyodavies 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\$ – tobyodavies Jan 28 '11 at 15:27
  • \$\begingroup\$ Aah, thanks, I'll look into that. \$\endgroup\$ – YasirA Jan 28 '11 at 15:35
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
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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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