Graph:
- Consists of a set of vertices (or nodes) and a set of edges connecting some or all of them
- Any edge can connect any two vertices that aren’t already connected by an identical edge (in the same direction, in the case of a directed graph)
- Doesn’t have to be connected (the edges don’t have to connect all vertices together): a single graph can consist of a few disconnected sets of vertices
- Could be directed or undirected (which would apply to all edges in the graph)
Tree:
- A type of graph (fit with in the category of Directed Acyclic Graphs (or a DAG))
- Vertices are more commonly called “nodes”
- Edges are directed and represent an “is child of” (or “is parent of”) relationship
- Each node (except the root node) has exactly one parent (and zero or more children)
- Has exactly one “root” node (if the tree has at least one node), which is a node without a parent
- Has to be connected
- Is acyclic, meaning it has no cycles: “a cycle is a path AKA sequence of edges and vertices wherein a vertex is reachable from itself”
- Trees aren’t a recursive data structure