Binary Trees

Definitions

full node

Perfect binary Trees

Height and nodes of a perfect binary tree

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.

  • More than half of the nodes are leaves.

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

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

Complete Binary Trees

Recursive definition of Complete Binary Trees

Height of a complete ninary tree

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$.

Filling a compete binary tree

Storage for complete binary trees


In [ ]: