8
$\begingroup$

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!!

$\endgroup$
7
  • $\begingroup$ Also, are you always talking about star graphs, or are you considering other tree shapes as well? $\endgroup$ Commented Jul 9, 2017 at 18:47
  • $\begingroup$ just for trees (no cycle should be present).. $\endgroup$
    – Anand Singh
    Commented Jul 9, 2017 at 18:51
  • $\begingroup$ To confirm, this is for general trees, not necessarily trees shaped the same way as the ones here (a single central node and a bunch of other nodes radiating outward?) $\endgroup$ Commented Jul 9, 2017 at 19:03
  • $\begingroup$ Yes, for general trees $\endgroup$ Commented Jul 9, 2017 at 19:07
  • $\begingroup$ Any recursive formula with explanation for this??....I need to implement this as a program. $\endgroup$ Commented Jul 9, 2017 at 19:15

1 Answer 1

8
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks a lot!...It helped :) $\endgroup$ Commented Jul 10, 2017 at 5:31
  • $\begingroup$ I got your point. But, myself, I still don't understand why multiplying all the values returned by the child node tree + 1 gives count of all the subtrees. I mean, why not using the combination in mathematics to calculate this thing. Why does multiplication gives the answer? $\endgroup$
    – asn
    Commented Aug 4, 2019 at 7:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .