Recursively creating a tree with binomial coefficient

Question

I'm trying to recursively populate a tree with integers (as shown in the link below). But I don't understand how to solve the inductive step using recursion.

PS. I have already created the recursive function to calculate the binomial coefficient

Thank you in advance!

Answer 1

The math notation in the picture at the link is a little obscure. But you want to implement that almost exactly. It's saying this:

Node buildTree(n) {
  Let tree be a new Node (with no children)
  For i from 0 to n - 1
    Let b = binomial(n, i)
    for b times:
      Add buildTree(i) as a child of tree
  return tree
}
   

The obscure part is that multiplication by some integer k in this "tree math" means "repeat the graph k times," and the summation means "add all as children" to an implicit parent node. This parent is the value of the expression.

Here's a development hint. Store a unique integer in each node as a label. Once you get that working, then write a little tree walker that prints out DOT language. When I did that for n=3, I got:

graph {
0 -- 1
2 -- 3
0 -- 2
4 -- 5
0 -- 4
6 -- 7
0 -- 6
8 -- 9
10 -- 11
8 -- 10
12 -- 13
8 -- 12
0 -- 8
14 -- 15
16 -- 17
14 -- 16
18 -- 19
14 -- 18
0 -- 14
20 -- 21
22 -- 23
20 -- 22
24 -- 25
20 -- 24
0 -- 20
}

You can see what that looks like by using online GraphViz here.

Answer 2

Pseudocode to illustrate recursive step

TreeNode getRootOfSomeFancyTree(n)
    TreeNode root = new TreeNode()
    if(n == 1) return root
    else for(i = 0; i < n; i++)
        //not sure of correct way to multiply an integer by a tree in your application
        int x = binomialCoefficient(n, i) * i
        //anyway, recurring is easy and safe provided x < n
        TreeNode subTree = getRootOfSomeFancyTree(x)
        //build the tree
        root.addChild(subTree)
    endfor return root