Deriving a formula to find the total items that can be present in a height balanced binary tree!
Algorithm design | Balanced binary tree
What is a height balanced binary tree?
Let’s start with understanding what is a height balanced binary tree first!
A binary tree will become height balanced when the difference between height of left and right subtree is 0.
In other words, in a height balanced binary tree all the positions in the current level will be filled. And any addition can be made in the tree only after filling a level completely.
For example, in the above picture, we have 3 levels (Starting from 0). Since the 3rd level is completely filled now (with 8 to 15), if we want to add a new item, we will have to create a new level and add.
Here is a good read to know more about balanced binary tree
Goal
Now we know that what a height balanced binary tree is, lets understand what we are trying to do here.
We want to derive a formula which will answer the below questions:
- How can we find the maximum number of items that could exist in a height balanced binary tree given that we know the height?
- How can we find the height of the balanced tree given we know the maximum number of items that could exist?
Analysis
If we make a table from this diagram listing down the relationship between level and number of items present at each level, we will have an interesting observation.
From our observation, it is clear that the number of items present at each level in the binary tree is equivalent to 2^n
From this, the total number of items present would be equal to
Total = 2⁰+ 2¹+2²+2³+…. 2^n
Going another level deep
Without concluding with this, lets draw another table with some more details
Detailed table explanation and observations
- Though we have only 1 item at level 0, we have taken an imaginary 1 additionally to get total items as 2 at this level (This is just for our convenience to identify a pattern. We will negate this later)
- By looking at the values in “Items@Level” column, we can easily define it as 2^level (To obtain this formula, we added the imaginary 1 earlier)
- The “Total” column indicates the maximum number of items that could be present at a given level. And it would be equivalent to number of items in the current level + total number of items from the previous levels
- And we can see that the values in “Total” column is always double of “Items@Level”. Hence we can define this as Max number of items = 2*(Items@Level)
- Since we added an imaginary 1 item earlier to derive the formula, lets negate that from the previous result. Now we will get something like this: 2*(Items@Level) — 1
Simplifying further
We have the below formula now
Max number of items = 2*(Items@Level) — 1
And we have already found from step 2 that, Items@Level = 2^level. On substituting this value in the above formula, we will get
Max number of items = 2*(2^level) — 1
Which could be denoted as
Max number of items = 2¹*(2^level) — 1
We know that a^m*a^n=a^(m+n). Applying this, we will get
Max number of items = 2^(level+1) — 1
Lets give level+1 a good name called h (Because level+1 indicates height of the tree 😊). Hence we get our final formula as
Max number of items = 2^h — 1
This is the function to find out the maximum items that can exist in a perfectly balanced binary tree!
The take away from this formula is that, the number of items that can exist in a balanced binary tree increases exponentially w.r.t height
Finding height from the max number of items present
Given there are max number of items present in a height balanced binary tree, what would be the height?
Lets try to derive this from the current formula we have. That is,
Max number of items = 2^h — 1
n= 2^h -1 , where n denotes Max number of items in height.
Simplifying this we will get
2^h = n+ 1
Applying log2 on both the sides, we will get
h = log2(n+ 1)
This is the function to find out the height of the height balanced binary tree using the total number of items that could exist.
The takeaway from this formula is that, the max height is logarithmic against maximum number of items in a height balanced binary tree.
I have tried my best to explain this derivation in a most simple way I could think of. I hope you learned something valuable today! 😊
