Write the shortest code that traverses a tree, breadth-first.
any way you like
a list of "names" of the nodes in correct order.
edit: Common Lisp (69 chars)
returns rather than prints the list and takes input as argument
Format is the same as below except it requires a 'dummy' root node like so:
Common Lisp: (95 chars)
This one reads and prints instead of using arg parsing
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
or equivalently -
Bash: (3 chars)
Using your "input any way you want", I'll take it as a list of nodes (one per line) in bredth first traversal order ;)
Edit: since i seem to need to defend the fact that this does in fact traverse, in bredth first order, a specific representation of a tree.
In this program trees are represented as a sequence of bytes, just as they are in any other language. It just so happens that using this representation of a tree, BFS is an extremely optimized operation - in-order iteration over those bytes. since the desired behaviour is outputting those bytes, cat does this in an efficient way.
Incidently, this exact representation is very commonly used to represent binary heaps, which are a type of tree.
For this to be a legitimate tree, the above code assumes a fixed number of children and a complete, balanced tree, if this is not the case then the following will work (still assumes binary tree, or at least fixed number of children):
Sed: (5 chars)
assuming the input is a line-based variant of the standard structure of a heap - i.e. root is line 0, its children are lines 1 & 2, 1's children are 3 and 4, 2's children are 5 & 6 and so on. blank lines represent missing children.
|show 7 more comments|
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
Haskell: 63 characters
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
The only possibly golf-like trick is using