CODEWITHSUNDEEP
data-structurestreebinary-treetreenode
Bobj-C
Bobj-C

Reputation: 5426

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

Upvotes: 5

Views: 33088

Answers (3)

jaxkewl
jaxkewl

Reputation: 213

A node at level n in a binary tree will have n ancestors. Proof by induction: Show P(0): A node at level 0 has no ancestors. (This is true because it is the root.) Show P(1): A node at level 1 has one ancestor. (This is true; the ancestor is the root, its father, which is at level 0.) Assume P(K): A node at level K has K ancestors. Its father is at level K - 1. Prove P(K+1): A node at level K+1 will have one more ancestor than the node at level K. The K+1th element will have a parent at level (K+1)-1, or level K.

Upvotes: 0

EnabrenTane
EnabrenTane

Reputation: 7466

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.

Upvotes: 4

atx
atx

Reputation: 5069

It sounds like you have it right. The minimum amount of nodes a binary tree can have is n and the maximum is 2^n-1

Upvotes: 1

Related Questions