Is there any proof for this question?
I don’t understand how minimum can be 2*h + 1 and maximum is 2^(h + 1) - 1
Course: Educative: Interactive Courses for Software Developers
Lesson: Educative: Interactive Courses for Software Developers
Hi @kalyan
My name is Shahrukh Naeem. I hope everything is going well with you. Thank you for reaching out about this. I will try my best to answer your query!
The height (h) of a tree is the number of edges from the furthest leaf to the root. In a full binary tree, every leaf is h edges from the root — the root and non-leaf nodes each have two children. Adding one more node would increase the height to h+1. A tree with a height (h) of zero has 1 node (the root) so, 2h+1−1 is 1. A full tree of height 1 has one root node and two leaf nodes, for a total of three nodes so, 2h+1−1 is 3.
Let’s consider the following tree to clarify it in a better way:
-
Maximum possible number of nodes in a binary tree having height h =
= 2^0 + 2^1 + 2^2 + 2^3 +……….+ 2^h (this forms a GP of h+1 terms)
= 1+2+4+8+……2^h
= 2^(h+1) - 1 -
We can prove the minimum number of nodes for a full binary tree of height h inductively. (We can readily verify that the minimum number of nodes for h=1 is 2×1+1=3, showing the base case to be true.) Assuming (inductively) that for h=𝑘 we have a minimum of 𝑁=2𝑘+1 nodes, if we add a node, it must branch from one of the leaves. But in order to maintain a full binary tree, we must add an additional node; that is, adding an additional level requires at minimum two more nodes. So, we will have 𝑁+2 nodes. Then, by our induction hypothesis 𝑁+2=(2𝑘+1)+2=2(𝑘+1)+1, which is what we wanted.
I hope that this guide is helpful. Remember that I am always available via message to help you with any difficulty you might encounter.
Regards,
Happy Learning 
2 Likes