Find Max Items and Max Height of a Completely Balanced Binary Tree

Consider a perfectly balanced binary tree. In such a tree, we never add items to a new level until all the positions in the previous level are filled up. We can easily and intuitively determine the number of items at any given level as a power of two. Level zero has only one item, level one has two items, and level two has four items, and so on.

Now, the total number of items in a perfectly balanced binary tree, up to level n would simply be the sum of the diverging geometric series where the multiplier is two. We could use the formula for a diverging geometric series to find the answer to this sum. However, it is not that hard to develop an intuitive understanding for this submission.

Let's make a simple table to keep track of the total number of items up to a given level. This zeroth level alone has just one node. As a thought experiment, imagine it has two items.

The first level has two items of its own, combined with two items of a previous level leading to a total of four items. The second level would have twice the items in the previous level, so we would have four items of its own, combined with the four items of the previous level resulting in a total of eight items.

Really, at any given level we have two to the power level own items plus two to the power level items from the previous level. The only trick for the final submission is that we need to remove the additional one we imagined at the zeroth level.

The level +1 variable has a nice name called "The height of the tree" leading to the simple formula two to the power h-1. We can code this up into a JavaScript function quite easily. The function takes a height argument, and we simply return the value based on the formula we just determined.

The key take away here is really that the number of items that can exist in a balanced binary tree, increase exponentially against the height.

Similarly, another key fact that should be at the tip of the tongue for an algorithm designer is given n items placed in a perfectly balanced binary tree, what would be the height? We start off with the derived formula for the max items against the given height. Let's call this n. SOAP over the -1 to the other side, and we get the max height H by taking log two on both sides.

Coring up this max height function, is just as easy as coring up the max items function. We take the number of items as an argument, and return the value as determined by a derived formula. The key take away here is that the max height is logarithmic against the number of items n in a balanced binary tree.

Use this height is 0(log n) fact, when analyzing algorithms that depend upon the height of a tree, for example, the methods of the heap data structure and binary search trees.