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:
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.
Types of Trees
- Segment Tree
- Fenwick Tree
- Spanning Tree
- Suffix Tree
- Disjoint Set Union
- K-d Tree
- Range Tree
A tree is a Connected Graph with no cycles.
A forest is a Graph with no cycles.
A leaf in 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.
Let be vertices in a tree . Then there exists a unique -path in .
Every edge in a tree or forest is a bridge.
If is a tree, then .
If is a tree with at least two vertices, then it has at least two leaves.
Every tree is bipartite.