## Basics

## Why height of a tree?

We want to figure out the height of a tree because that is the worst case scenario of a search. It is the max number of step it takes to find an item.

For example, if we find the item at the root node. Great! it took only 1 step. If we need to find another item and took 2 or 3 steps, okay average. But what if the key we’re looking for is at the very bottom of the tree at a leaf node? Then we’d have to step h times where h is the height of the tree.

In the example below where the height is 3, the worst case scenario is for us to step 3 times to a leaf node to either find a match or denote that whatever we’re trying to find is not found.

## Proof

The number of nodes in a tree is denoted by n

1 + 2^1 + 2^2 + 2^3 + 2^4 … + 2^h = n

This is also true:

n = 2^(h+1) – 1

Reminder that height of a node at the leaf node is 0…and so on. as shown in the first image of this article.

Reminder that height of a node at the leaf node is 0…and so on. as shown in the first image of this article.

Hence

1 + 2^1 + 2^2 + 2^3 + 2^4 … + 2^h = 2^(h+1) – 1

n = 2^(h+1) – 1

n + 1 = 2^(h + 1)

*note that lg has base of 2*

We apply lg on both sides:

lg (n + 1) = (h + 1) lg 2

Hence, because lg 2 = 1, then lg (n+1) = h + 1

lg (n+1) – 1 = h

Hence by definition of O notation where f(x) = c * g(x) for some coefficient c,

We can say that h = lg(n).

## Usage

In order to find out the max number of steps from root to bottom of the tree, from the proof above, we use the equation:

h = lg(n + 1) – 1, where n is the total number of nodes in a balanced tree.

Reminder. The total number of nodes n = 2 ^ (h + 1) – 1 as shown in the image above.

if we want to find the total number of steps it takes from root to bottom, we must simplify the equation for height h.

### Calculating height of tree

given that total number of nodes n

n = 2 ^ (h + 1) – 1

as shown in the image above.

2 ^ (h + 1) = n + 1

(h + 1) lg 2 = lg (n + 1 )

since lg 2 = 1

then h = lg (n + 1 ) – 1

For example, given number of nodes n = 31, total number of height (or vertices) is n = lg(31 + 1) – 1 = 4 steps.

### Calculating terms, or node levels

If you want to find terms or level of nodes in the tree, we use serial geometric equation as defined by:

S = a + ar + ar^2 + ar^3 + … + ar^n-1

where ‘a’ is the initial number of nodes.

‘r’ is the rate of growth.

term1 + term2 + term3 + term4 + term5

1 + 1(2^1) + 1(2^2) + 1(2^3) + 1(2 ^4) = 1 + 2 + 4 + 8 + 16 = 31

A term represents a node level.

The equation is

s = l_0 * (q^n – 1)/(q-1)

where q is the rate of growth and n is number of terms, or node levels

l_0 is the initial number of nodes.

hence, l_0 = 1, q = 2

S = 1*(2^n – 1)/(2-1) = 2^n – 1

S = 2^n – 1

S + 1 = 2 ^ n

lg (S+1) = n * lg 2

since lg 2 = 1

lg (S+1) = n

Hence number of node levels is defined as:

n = lg(S + 1)

NOTE: that node levels vs height is VERY different things.

Height is number of vertices. whereas node levels is each floor of the tree

## Balanced Tree

In order to have a balanced so that we can have O(log n), we can use:

- AVL
- Red Black Tree