how many nodes can a binary tree have at level n? Use induction to prove the answer
This is a homework and i didn't have much time to spent on it but I know some of the answer and need a little help plz
i'm thinking like this assume we have:
1 node ----> Level 1
2,3 nodes ----> Level 2
3,4,5,6,7 nodes ----> level 3
4,5,6,.....,15 nodes ----> Level 4
5,6,7,8,9,.....,31 nodes ----> Level 5
node(s) interval from [ min=X node(s) TO max = 2^X - 1 node(s) ] where X represent the level
from now on i'm confused how to complete
Answer
As I recall to use induction you have to prove the Nth case and the N + 1th case. And we see for any N that the N + 1th level has exactly twice as many. Thus shown by 2^(N + 1) / 2^N = 2
The total number of nodes can be found by taking the sum from n = 0 to N - 1 of 2^n
You probably want a more conclusive and verbose answer, but thats the gist.