[Algorithm] Find Max Items and Max Height of a Completely Balanced Binary Tree

A balanced binary tree is something that is used very commonly in analysis of computer science algorithms. In this lesson we cover how to determine the maximum number of items it can accommodate.

We follow this with a discussion on the maximum height of a binary tree given we need to accommodate n items.

                O
           ╱       ╲
         ↙            ↘
       O                O
     ↙   ↘           ↙    ↘
   O       O        O       O
 ↙  ↘    ↙  ↘    ↙  ↘    ↙  ↘
O    O   O   O   O    O   O   O

level 0 : 1 (2 ^ 0)
level 1 : 2 (2 ^ 1)
level 2 : 4 (2 ^ 2)
...

2^0 + 2^1 + 2^2 + 2^3 .... + 2^n
=>

 

Height of tree  |  Level  |  Items in level      |    Total
     1               0             1  (+1 lie)          2
     2               1             2                    4
     3               2             4                    8
     4               3             8                   16

2^level + 2^level - 1
2*(2^level) - 1
2^(level + 1)  - 1
2^h - 1

 

/**
 * Returns the max items that can exist in a perfectly balanced binary tree
 */
export function maxItems(height: number) {
  return 2 ** height - 1;
}

/**
 * Returns the max height of a balanced binary tree given n items
 */
export function maxHeight(items: number) {
  return Math.log2(items + 1);
}