Graph versus tree

A rooted tree is a special kind of graph: connected and acyclic with one distinguished root. This page contrasts general graphs with that hierarchical model—mirroring Tree versus graph from the tree track.

On this page
  • Graph vs Tree comparison table
  • Trees inside graphs — spanning trees & uses
  • Choosing the right model

1) Graph vs Tree (comparison table)

Graph vs Tree — feature comparison
Feature Graph Tree
Definition Collection of vertices (nodes) and edges. Special type of graph with hierarchical structure.
Connection May or may not be connected. Always connected.
Cycles Can have cycles. No cycles
Number of edges Any number. Exactly n − 1 edges (for n nodes).
Root node No root concept. Has a root node.
Parent-child relation Not defined. Clearly defined.
Path between nodes Multiple paths possible. Exactly one unique path.
Direction Can be directed or undirected. Usually directed (parent → child).
Structure Network-like. Hierarchical (tree-like).
Traversal BFS, DFS. Inorder, Preorder, Postorder, Level order
Examples Social networks, maps. File system, organization chart.

2) Trees sit inside graphs

Every tree is an undirected graph with no cycles. Algorithms on graphs often build a spanning tree (BFS tree, DFS tree, MST) even when the original graph has extra edges—those trees summarize reachability or minimum cost structure.

For strict hierarchies (BST, heap shape, folders), stay in the tree tutorial. For roads, dependencies with cycles, or social links, stay in this graph track—see also graph notes.

3) When to choose which

Choosing a model
Choose a graph when… Choose a tree when…
You need multiple routes, cycles, or arbitrary connectivity. Data is strictly hierarchical (one parent per node).
Problem mentions shortest paths, SCC, or network flow. Problem mentions BST order, heap, or parse structure.
Edges may be directed or weighted in messy ways. You only traverse down/up the hierarchy from a root.

Key takeaway

Graphs generalize trees: add edges and cycles and you leave the pure hierarchy—your representation (adjacency list) and algorithms (BFS, DFS, shortest paths) reflect that extra complexity.

Next up: Graph types · Graph traversal overview · Tree versus graph (tree track)