# Random and k-ary tree Ruby generator

The title might sound a little barbaric and some of you might wonder, **what on earth is a k-ary tree? **It is really simple: as per the Wikipedia article, “a k-ary tree is a rooted tree in which each node has no more than *k* children”. For instance, a 3-ary tree is called a ternary tree and each node has a maximum of three children:

A random tree will have, for each node, a random amount of children, it’s quite simple.

# Ok, but why would I need a k-ary or a random tree random generator?

If like me you are into computer science and having fun with algorithms, you must have come across *tree traversal**s* , in particular *breadth-first search* and *depth-first search*. You might be fiddling with different versions of your code, trying recursive and iterative approaches. And you probably always test your code on the same tree, for a simple reason: it’s quite a long process to write a tree manually. For instance, to code the following small tree in Ruby,

you would have to hard code the following:

So what if you want to test your tree traversal algorithms on different trees, including large ones, some very wide, some very deep, without having to laboriously hard code your tree ? Well, you would definitely need a tree generator :) Let’s start with a simple version:

# k-ary tree generator

Then you can call the method on any array, specifying k as the number of children per node, for example :

would output the following tree:

Not so easy to read, so here is a better representation:

and its graphic representation:

If you would choose k =12, you would get the **shallowest possible tree **with a depths of one and a width of 12 will all the nodes on the same line, all direct children of the first node (1).

On the other hand if you choose k = 1, your will have the **deepest possible tree** (depth 12 in this case), as your tree will be in a straight line from the root (each node will have a maximum of one child only).

Finally, k = 0 will return only the trunk of the tree, i.e. the first node, as it will have no children .

**Ok, but this kind of tree is a bit boring:**

- it always chooses the items of the array in the same order
- each node always have the same number of children (if the tree is “full”)

**We can change that an generate more funky trees, with a fully random tree generator, as follows:**

# Random tree generator:

Then you can call the method on any array, specifying k as the maximum number of children per node, for example :

and you get your random tree, for instance:

or:

or:

Well, I will stop here, I am sure you get the idea by now, it’s random and you can now build vast beautiful trees in a blink to test your tree traversals :)

Feel free to to build a graphical representation of these trees if you have nothing better to do - which would be surprising- but don’t be mad at me if I didn’t ;)

PS: Any ideas of refactoring, code improvement or variations are most welcome!