Number of "Sub trees" of a given tree

Question

Given a tree, how can we find the number of "sub trees" of this tree. Following example illustrates the previous statement. eg:

Consider a tree with 3 nodes and having the following edges:
    0-1
    1-2
Then the number of subtrees possible are 7. The subtrees are as follows:
here x-y denotes that: there is an edge between node 'x' and node 'y'.
{},{0},{1},{2},{0-1},{1-2},{0-1-2}

If we consider a tree with 5 nodes having following edges:
    0-1
    1-2
    1-3
    1-4
This tree will have 21 subtrees. I have checked it by counting and it is correct.

I would like to know the logic behind calculating the number of subtrees (some sort of formula that one can derive or any another trick rather than manually counting it). Here is link to question Thanks in advance!!

Answer 1

There is always 1 empty set subtree and for each leaf, exactly 1 subtree consisting of the leaf.

Say A is some node which isn't a leaf, and that it's children are a1, a2, ..., ak. Say that we've already counted the number of subtrees of the maximal subtree rooted at each of these (i.e., which include these but no parent). Say these numbers are n1, n2, ..., nk.

Then the maximum number of subtrees rooted at A is (n1+1) * (n2+1) * ... * (nk+1).

In your example, vertices 2, 3, and 4 all have 1 subtree rooted at them because they're leaves. Vertex 1 has (2 * 2 * 2) = 8 subtrees rooted at it, and Vertex 0 has 8+1 = 9 subtrees rooted at it. Together with 1 empty set that gives us 9 + 8 + 3 + 1 = 21.

To clarify how this works: Subtrees rooted at leafs are clear. The (n1+1)(n2+1)...*(nk+1) comes about because we can independently have all, part, or none (the +1) of any of the immediate descendant subtrees in the parent subtree.

The actual algorithm to use this to calculate the total is to start with the leafs, then use the formula to calculate successive parents until you get to the ultimate root.