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.
From MATH239
Definitions:
Tree
A tree is a Connected Graph with no cycles.
Forest
A forest is a Graph with no cycles.
Leaf
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.