CODEWITHSUNDEEP
data-structuresbinary-tree
Sahaj
Sahaj

Reputation: 43

Minimum nodes in a n-ary tree

I know the formula for finding the maximum number of nodes in a n-ary tree given the height ( a tree containing either n nodes or none per node): (N^h+1)-1/(N-1). But how would you find the minimum number of nodes in a tree given the height and N.

Upvotes: 2

Views: 1246

Answers (2)

John Coleman
John Coleman

Reputation: 52008

I am assuming that this isn't homework (since you didn't phrase it as if it were) but is to satisfy your curiosity.

To start the tree you need 1 node. To keep it growing you need a minimum of N new nodes per level. Since you are trying to minimize the total number of nodes, the total is thus

1 + N + N + .... + N = 1 + h*N

Upvotes: 1

qwr
qwr

Reputation: 10958

Intuitively, the minimum number is a tree in which only one node has children and the rest have none.

Upvotes: 1

Related Questions