lulRber of nodes on the levels of a binary tree evnonentially as we go down the

Question

lulRber of nodes on the levels of a binary tree evnonentially as we go down the tree. From this simple observation, we can ve the following properties relating the height of a binary tree T with its number A detailed justification of these properties is left as Exercise R-8.8. the number of nodes, nu bi height of T, respectively. Then T has the following properties: Proposition 8.8: LetT be a nonempty binary tree, and let n, ng, ny and h denote umber of nodes, number of external nodes, number of internal nodes, and 3. h Sni S21 4. log(n 1)-1

Explanation / Answer

Solution:

Base case:

When there is only one node in the binary tree then

the number of nodes = 1= 2^(h+1)-1 = 2^1 - 1= 1

number of external nodes= 1

number of internal node = 0

and height is also 0

Inductive case:

At height 1

Number of nodes = 2^(1+1) - 1 = 3

number of external nodes= 2

number of internal node = 1 (root)

At height 2

Number of nodes = 2^(2+1) - 1 = 7

number of external nodes= 4

number of internal node = 3

.

which means the numebr of nodes in a binary tree can be 2^(h+1) - 1, please note that this is the maximum it can be

minimum case will have skewed binary tree which means the number of nodes = height +1

so the prosition is proved

h + 1 <= n <= 2^(h+1) -1

Now

part 3

since we have proved h + 1 <= n <= 2^(h+1) -1

and we know that

n= nE+ nl

which means

nl = n-ne

which means max 2^(h+1) - 1 - 2^h = 2^(h) -1

and

h+1-1 = h

h <= nI <= 2^(h) -1

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.