CODEWITHSUNDEEP
treebinary-tree
rayhanrjt
rayhanrjt

Reputation: 1

How to calculate the number of node if the height of a complete binary tree is N.....A.2^n B.2^n-1 c.2^(n+1)-1 D. N

If the height of a complete binary tree is n, then How many Node in the tree have. A.2^n B.2^n-1 c.2^(n+1)-1 D. N

Please Explain regarding the answer.....

Upvotes: 0

Views: 115

Answers (2)

lrleon
lrleon

Reputation: 2648

Because the last level could be not full, you cannot give an exact number. But you could give an interval. Let N the number of nodes of a complete tree and n its height. Then

1 + 2 + 2^2 + ... + 2^(n-2) < N <= 1 + 2 + 2^2 + ... + 2^(n-2) + 2^(n-1)

Upvotes: 0

Charlieface
Charlieface

Reputation: 71578

It's a large range.

The minimum is N, given you can have a single node on each level. The maximum, if every level has two nodes, is N ^ 2 - 1.

Upvotes: 1

Related Questions