# First of All…

A tree is just a special type of graph, namely a **connected acyclic graph**.

# Terminology

## Height of a Node

- Number of edges on the
*longest*path from this node to a leaf - Leaves have height 0

## Height of a Tree

- Height of the root

## Depth of a Node

- Number of edges on the path from this node to the root
- Root has depth 0

## Levels of a Tree

- A tree has Height + 1 levels
- Root is at level 1

# Binary Trees

TODO: draw example binary tree with e.g. 10 nodes

- Height of a binary tree with $n$ nodes: $\lfloor\Log n\rfloor$
- Maximum number of nodes in a binary tree with $n$ levels: $2^n-1$