Tree versus graph
A tree (rooted, as in this tutorial) is a special kind of graph. Use the tables below to see when structure is forced (tree) versus when you need the full generality of graphs.
- Structural comparison (table)
- Algorithm and storage hints
- Relationship: tree ⊆ graph
1) Structural comparison
| Property | Tree (rooted) | Graph (general) |
|---|---|---|
| Cycles | None — acyclic. | Allowed (depends on problem: DAG, multigraph, etc.). |
| Root | Exactly one node with no parent. | May be undirected (no root) or multiple sources. |
| Parent | Each non-root has one parent. | A node can have many neighbors; not necessarily hierarchical. |
| Path | Unique simple path between any two nodes. | Multiple paths possible if cycles exist. |
| Edges | Typically n−1 edges for n nodes (connected tree). |
Any count from 0 up to O(n²) (dense). |
2) Every tree is a graph
Formally, a (finite) tree is a connected acyclic undirected graph; adding a root and parent pointers yields the usual CS “tree” for algorithms. If you need shortest paths in arbitrary networks, social graphs, or road maps, you usually work with graphs (BFS, Dijkstra, etc.)—see your graph tutorial and graph notes when you leave the strict tree model.
3) When to choose which
| Choose a tree when… | Choose a graph when… |
|---|---|
| Data is naturally hierarchical (one parent). | Entities have many-to-many or bidirectional links. |
| You need BST order or heap shape. | You need cycles (dependencies, circuits). |
| Traversal is DFS from root or level order on a subtree. | Traversal is BFS/DFS from arbitrary start with visited sets. |
Key takeaway
Trees are the acyclic hierarchical corner of graph theory—simpler to reason about and often easier to implement recursively. Move to graphs when the real world has cycles or non-tree connectivity.
Next up: Tree types · Tree traversal methods · Tree representation