# Tree

A tree is a special kind of directed Graph.

- Root node has no parent
- Each node has 0 or more children

We can sub-categorize trees into:

- N-ary trees
- Binary Tree
- Binary Search Tree

Leaf nodes are nodes that have no children.

SUPER IMPORTANT PROPERTY: There is only 1 path between any two nodes on the tree. This is not the case with a Graph.

### Depth vs. height

**Height** of a node (looking up from leaf node) → length of the longest path from it down to a leaf

- Leaf node has height 0

**Depth** of a node (looking down from root) → length of the path from the root to it

- Root has depth 0

### Storing Trees as Arrays

It is very common to store trees as arrays. The way they are represented is dependent on the tree.

We also saw this in CS240, storing the Heap as an Array.

### Types of Trees

- Segment Tree
- Fenwick Tree
- Spanning Tree
- Suffix Tree
- Disjoint Set Union
- Treap
- Quadtree
- K-d Tree
- Range Tree

### Related

### From MATH239

**Definitions**

Tree

A

treeis a Connected Graph with no cycles.

Forest

A

forestis a Graph with no cycles.

Leaf

A

leafin a tree is a vertex of degree 1.

A tree is a “minimally-connected graph”: it is connected, but removing any edge disconnects it.

**Theorems and Lemmas**
There are all these theorems and lemmas that you should be able to prove.

Lemma 5.1.3

Let $x,y$ be vertices in a tree $T$. Then there exists a unique $x,y$-path in $T$.

Lemma 5.1.4

Every edge in a tree or forest is a bridge.

Theorem 5.1.5.

If $T$ is a tree, then $∣E(T)∣=∣V(T)∣−1$.

Theorem 5.1.8

If $T$ is a tree with at least two vertices, then it has at least two leaves.

Lemma 3

Every tree is bipartite.