Binary Trees

Definitions

full node

The number of nodes of a perfect binary tree with heigh $h$ is

$$n = 2^{h+1} - 1$$

The important property of perefect bnary tree is that always $\lfloor \frac{n}{2} \rfloor + 1$ of nodes are leaves.

The height ($h$) of a perefect tree with $n$ nodes can be computed as

$$h = \lg(n+1) - 1$$

The height of a compltete tree ($h$) in terms of the number of nodes ($n$) os given by:

$$h = \displaystyle \lfloor \lg(n) \rfloor$$

where $\lg$ is the logarithm function with base $2$.



In [ ]: