CODEWITHSUNDEEP
data-structurestreecomputer-scienceabstract-data-type
Dave
Dave

Reputation: 421

Finding max and min nodes possible in a tree of depth k and with a branching factor of n

I have a tree of depth k and branching factor of n. I've been trying to find a general formula for:

  1. Maximum number of nodes possible in this tree
  2. Minimum number of nodes possible in this tree

Any suggestions? Thanks in advance.

Upvotes: 0

Views: 2313

Answers (2)

leo
leo

Reputation: 1117

To calculate the max number of nodes assume every new level is full. In the first level you have 1 node, in the second n nodes, in the third you have n^2 nodes (n for each of the previous n), in the fourth you have n^3 (n for each of the previous n^2)...

This gives you sum(i=1, k-1, n^i) + 1 ==> (n(n^k -1))/(n-1) + 1

The min number of nodes is of course 0 :)

Upvotes: 0

corsiKa
corsiKa

Reputation: 82579

I hate to say it, but this is a trivially simple question for a data-structures course. I don't want to be rude or mean or anything of the sort, but this is about as simple as these questions get.

But you asked for suggestions, not solutions. This is a good thing. :-)

I would start with making sure you know the definition of branching factor. Then I would draw a pick a couple easy values for k,n like (1,1) (2,2) (3,2) and see what the result is. I promise you a pattern will emerge!

Edit:

So you have a grasp of the branching factor. Let's look at the minumum.

If you have a depth of k, you know that you can traverse along k different nodes right? So if none of those nodes have any other children, and the end node has no children, what can you say about the nodes there?

Okay that was easy. The maximum is a bit harder, but still fairly straightforward. The easiest way to look at it is to think less like a tree. Trees have a top and go down. Instead, think of this as a series of concentric circles, each circle representing a level of depth.

Let's start with (depth = 1). You know you're going to have just one node, right? I mean it can't have any children, because you're limited to 1 depth! Now, let's look at depth of 2. The starting node can have n (assuming n is the branching factor) child nodes. So that would be n + 1.

Now if we add one more to that, we end up with n nodes on the "outside ring" each of which can have n children. So you end up with n*n + n + 1.

On each successive ring, you end up with (nodes added last time) * (branching factor) + all existing nodes. Now can you think of a way to express that as a formula?

Upvotes: 1

Related Questions