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 traversals , 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:
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!