Problem: Find the number of unique M-ary trees that can be constructed with n nodes.
Solution:
First, lets consider a specific case, the ternary tree. Here are all possible binary trees with 1 node:
o
There is only one possible tree, the root itself. Now consider trees with 2 nodes:
_tree____tree 2____tree 3
__o______o________o
o________o__________o

Makes sence, because the tree has 3 possible directions, so there are three different way to
connect a root and its child. Now lets think about all the possible places where we can add
an extra node to make it a 3-node tree. Forming a random tree with 3 nodes will probably
not do any good. So we have to keep organized, and add an extra node in a fixed manner.
This will be the way: given a tree, count all the possible places where it is possible to add
an extra node, but only do it for anything that is right of the leaf node of tree we are currently working with, or add it directly to
the leaf. So:


o
__o
__o
There is nothing to the right, and the only place to add an extra node is to the leaf itself, as
such:
o_________o__________o
o____OR___o____ OR___o
__o_______o____________o
Total: 3 ways (call it Total1)
Now work with the next tree:
o
o
In this case, it is possible to add 1 extra node to the right part, or the root itself (so that the added node is the root's right child), as such:
o
o o
And, of course, it is also possible to add three extra nodes to the leaf:
__o____o___o
__o____o___o
o______o_____o
Total: 1+3 = 4 ways (call it Total2)
Now, only one tree left to examine:
__o
o
In this case, we can add an extra node to the right of the root, and to the middle of the root:
__o_____________o
o___o_________o__o
And again, it is possible to add 3 extra nodes to the leaf:
____o_____o_____o
__o____o_____o
o______o_______o
Total: 3+2 = 5 (call it Total3)
Now the overall total = Total1+Total2+Total3 = 3+4+5 = 12
We are not really interested in the final answer, '12'. The key is '3+4+5'. Every number is strictly
increasing by one. Coincidence? I think not. :)) In fact it makes sense, because taking into
account the way we add extra nodes, this is exactly what should happen. When we considered
the first tree, it has a rightmost node, so the only way to add something to the tree, was to add it
to that right-most node. And since we are dealing with a ternary tree, which only has 3 possible
directions, there are 3 ways to add an extra node. If it was an M-ary tree, then there would
be M possible ways to add an extra node to a similar tree (looking like a diagonal line from left
to right). The second tree is essentially the first tree, but with a node shifted to the right, which
opens up an extra space for that extra node. So now there are 3+1 possible spaces for an extra node. So for M-ary it would be M+1 then. And the third tree is, again, the first tree, with root's child shifted to the right two times. So noew there are 3+2 possible spcaces for an extra node.
And again, it would be M+2 for M-ary tree (if M>2). Now, since M-ary tree can have any number of directions, it might keep going, as M+3, and M+4, and so on, depending what M is.
Every time we add an extra node to the tree, we increase the number of potential spaces by
3, or M in case of M-ary tree. So, if we could add 3 nodes to a tree with n possible nodes,
then for each of those 3 nodes, we could add 3, 4, and 5 nodes for a tree with n+1 possible nodes.
For n+2, we would expand every number further, so it would be 3,4,5, 3,4,5,6, 3,4,5,6,7.
So we expand each number i as a sum from 3 to i+2 (for ternary tree)
So expanding 3 we would get 3+4+5
4: 3+4+5+6
etc.
The same works for M-ary tree, but we expand each number i as a sum from M to (i+(M-1)).
Knowing how to go from n to n+1, I coded a python function, first for the ternary tree (n>=2),
and then it is easy to generalize for the M-ary tree (n,M>=2):
(This blog formats the lines in a very annoying manner, and doesn't display my python functions properly,
so I included this picture below instead. The "_" instead of spaces in the tree diagrams were for the same reason)
No comments:
Post a Comment