Trees and Graphs as a First Look
A tree is a hierarchy with one root and no cycles; a graph drops that restriction entirely — and safely exploring either one means tracking what's already been visited.
By the end of this lesson, you can
- Explain the vocabulary of a tree — root, parent, child, leaf — and how it differs from a general graph
- Represent a small tree and a small graph using nodes and references, and trace a traversal of each
- Explain why safely exploring a graph requires tracking which nodes have already been visited
Why it matters
An org chart, a file system, and a social network are all naturally made of connected things — but they’re connected in fundamentally different shapes. An org chart has one CEO at the top and no loops; a social network has no single “root” and friendships can loop back on themselves. Trees and graphs are the mental models for these two shapes, and the previous lesson’s nodes-and-references idea extends directly to both.
Mental model
A tree is a hierarchy: one root node, each node can have children, and a node with no children is a leaf. Every node has exactly one parent, except the root, which has none — and there are no cycles.
root = {"value": "CEO", "children": []}
vp_eng = {"value": "VP Engineering", "children": []}
vp_sales = {"value": "VP Sales", "children": []}
root["children"] = [vp_eng, vp_sales]
print(root["value"])
for child in root["children"]:
print(child["value"])CEO
VP Engineering
VP SalesA graph drops the hierarchy requirement entirely: nodes connect to each other in any pattern, cycles are allowed, and there’s no single root. A friendship network is a natural graph — represented here as each person’s name mapped to a list of their direct connections:
graph = {
"Ada": ["Grace", "Linus"],
"Grace": ["Ada", "Margaret"],
"Linus": ["Ada"],
"Margaret": ["Grace"],
}
print(graph["Ada"])['Grace', 'Linus']Notice "Ada" appears in "Grace"’s list too — a cycle. A tree
never has this; a graph often does.
Trace it — exploring the graph safely
Finding everyone reachable from Ada means following connections outward, using a queue (from the stacks and queues lesson) to track who still needs visiting, and a set (from sets and uniqueness) to track who already has:
visited = {"Ada"}
to_visit = ["Grace", "Linus"]
while to_visit:
person = to_visit.pop(0)
if person in visited:
continue
print(person)
visited.add(person)
for neighbor in graph[person]:
if neighbor not in visited:
to_visit.append(neighbor)Grace
Linus
Margaret| Step | to_visit before | Person processed | visited afterward |
|---|---|---|---|
| 1 | ["Grace", "Linus"] | Grace — neighbor Ada already visited, skipped; Margaret added | {Ada, Grace} |
| 2 | ["Linus", "Margaret"] | Linus — neighbor Ada already visited, nothing added | {Ada, Grace, Linus} |
| 3 | ["Margaret"] | Margaret — neighbor Grace already visited, nothing added | {Ada, Grace, Linus, Margaret} |
Because visited started out already containing "Ada", Grace’s
"Ada" neighbor is filtered out before it’s ever added back to
to_visit at all. Together, the two visited checks — filtering a
neighbor before adding it, and skipping a person already processed —
are what keep the Ada ↔ Grace cycle from causing endless repeats.
Check your understanding
Or reveal the answer without checking
Answer:A leaf
A node with no children is a leaf — the end of a branch, with nothing hanging further down from it.
Or reveal the answer without checking
Answer:A graph can have cycles, so following every connection without tracking visited nodes can revisit the same nodes forever; a tree has no cycles to loop through
A tree's lack of cycles means a straightforward walk from the root naturally terminates. A graph's cycles mean the same walk can revisit nodes indefinitely unless visited nodes are tracked and skipped.
Practice: warm-up
For this three-level tree, write down: the root, all the leaves, and one node’s parent.
root = {"value": "Fruit", "children": []}
citrus = {"value": "Citrus", "children": []}
berry = {"value": "Berry", "children": []}
orange = {"value": "Orange", "children": []}
root["children"] = [citrus, berry]
citrus["children"] = [orange]Stuck? Reveal one hint at a time.
Hint 1
The root is whichever node nothing else points to as a child.
Hint 2
A leaf is any node with an empty children list, once every children assignment above has run.
Reveal the answer
Try the problem yourself before reading this. There is often more than one reasonable approach — treat this as one worked example, not the only correct answer.
Root: Fruit
Leaves: berry, orange (both have empty children lists)
orange's parent: citrusPractice: apply it
This code is meant to explore the graph starting from "Grace", but it
never tracks which nodes have been visited:
to_visit = ["Grace"]
while to_visit:
person = to_visit.pop(0)
print(person)
for neighbor in graph[person]:
to_visit.append(neighbor)Or reveal the answer without checking
Answer:It runs forever, since Grace and Ada keep re-adding each other to to_visit with no visited check to stop it
Without checking visited before adding a neighbor, the Ada <-> Grace cycle keeps feeding both names back into to_visit indefinitely — the loop never runs out of work.
Modification challenge: fix this by adding a visited set, the
same way the lesson’s traversal did, so each person is printed exactly
once.
Summary
- A tree is a hierarchy — one root, no cycles, every node has exactly one parent except the root.
- A graph drops that restriction: any connection pattern is allowed, including cycles and multiple paths between nodes.
- A queue plus a visited set is enough to explore a graph safely, printing each reachable node exactly once.
- Skipping the visited check isn’t a minor omission — on a graph with a cycle, it can make a traversal run forever.