Introduction to Trees
What is a graph?
A graph is a collection of nodes (also called vertices) connected by edges. Nodes hold the data, edges express a relationship between two nodes.
graph LR A((A)) --- B((B)) B --- C((C)) C --- A C --- D((D))
This graph contains a cycle (A – B – C – A), so there is more than one way to get from A to C.
What is a tree?
A tree is a graph with two additional constraints:
- It is connected: every node can be reached from every other node.
- It has no cycles: there is exactly one path between any two nodes.
A consequence: a tree with n nodes always has exactly n − 1 edges.
In computer science we almost always use rooted trees: one node is declared the root, and the tree is drawn top-down.
graph TD A((A)) --> B((B)) A --> C((C)) B --> D((D)) B --> E((E)) C --> F((F))
Terminology
| Term | Meaning | In the tree above |
|---|---|---|
| Node | An element of the tree that holds data | A, B, C, D, E, F |
| Edge | A connection between two nodes | A→B, A→C, B→D, … |
| Root node | The single top node; it has no parent | A |
| Parent | The node directly above another node | A is the parent of B and C |
| Child | A node directly below another node | B and C are children of A |
| Sibling | Nodes that share the same parent | B and C; D and E |
Examples
File system
Directories are inner nodes, files are leaves; / is the root.
graph TD root["/"] --> home["home"] root --> etc["etc"] home --> norwin["norwin"] norwin --> docs["documents"] norwin --> notes["notes.txt"] etc --> hosts["hosts"]
DOM (Document Object Model)
The browser represents an HTML document as a tree of elements.
graph TD html["html"] --> head["head"] html --> body["body"] head --> title["title"] body --> h1["h1"] body --> ul["ul"] ul --> li1["li"] ul --> li2["li"]