Historical Context & Motivation
Long before computers existed, people organized information in hierarchical structures. Family trees, organizational charts, and biological classification systems all show a pattern where one item branches into several related items. When computer scientists began building software in the mid-twentieth century, they needed a way to represent these branching relationships inside a machine's memory. The tree data structure became one of the most important tools for solving that problem.
Early programming languages stored data in flat lists or arrays, which work well for ordered sequences but struggle to capture parent-child relationships. As applications grew more complex — file systems, databases, compilers — developers needed structures that naturally express hierarchy. Two main strategies emerged: linking individual node objects together with references, and recording connections in an adjacency list. Both approaches are still used every day in modern software.
The core question this lesson addresses is straightforward: if you have hierarchical data — like a family tree or a folder structure — how do you actually store it in Python so your program can traverse and manipulate it? Understanding the two main representation strategies will give you the foundation to tackle any tree-based problem.
Core Principles & Definitions
Before diving into code, you need to understand a few key terms. A tree is a collection of items called nodes connected by edges. Unlike a general graph, a tree has no cycles — there is exactly one path from any node to any other node. Every tree has a single root node at the top, and nodes with no children are called leaves.
Node (Vertex)
Edge
Root
Node/Object Representation
Adjacency List Representation
Visual Explanation — Node/Object Representation
The diagram below illustrates a simple tree with five nodes and how it maps to Python objects. Each rounded rectangle represents a TreeNode object. Inside each object you can see the stored value and an arrow pointing to its children. The root node "A" has two children, "B" and "C". Node "B" itself has two children, "D" and "E", while node "C" is a leaf.
TreeNode object stores a value and a list of references (pointers) to its children. The arrows show how parent objects link to child objects in memory. Leaves have empty children lists.Notice how the tree's shape is encoded directly in the objects themselves. Node A's children list contains references to the B and C objects. If you want to find all of A's descendants, you start at A and follow the children links downward. This approach is intuitive because the code mirrors the visual structure of the tree.
How It Works — Code Patterns
Pattern 1: Node/Object Representation
In Python, you define a class to represent each node. The simplest version stores a value and a list of children. For a binary tree — where each node has at most two children — you might use explicit left and right attributes instead of a list. Here is the general-purpose version:
class TreeNode:
def __init__(self, val):
self.val = val
self.children = []
Each instance holds its own data (val) and a list of references to child TreeNode objects.Pattern 2: Adjacency List Representation
An adjacency list uses a Python dictionary to store the entire tree. Each key is a node's value, and the corresponding value is a list of its children's values. You do not create separate class instances — the structure lives entirely inside one dictionary.
tree = {
"A": ["B", "C"],
"B": ["D", "E"],
"C": [],
"D": [],
"E": []
}
This single dictionary encodes the same five-node tree. Finding node B's children is as simple as tree["B"], which returns ["D", "E"].Detailed Breakdown — Node Objects vs. Adjacency Lists
The diagram below places the two representations side by side for the same tree, making it easy to see how each approach encodes the same relationships in a different format.
TreeNode instances. Right: the adjacency list stores the same relationships in a single Python dictionary. Both encode exactly four edges connecting five nodes.When you look at the left side, notice that navigating the tree means following object references — you literally "walk" from one object to the next through the children list. On the right side, navigating means dictionary lookups: you ask "who are B's children?" and the dictionary answers instantly. Both approaches give you the same information; the choice between them often comes down to what operations you need to perform most often.
| Feature | Node/Object | Adjacency List |
|---|---|---|
| Data stored | Value + children references per object | Dictionary mapping each node to its children |
| Find children | Access node.children | Lookup tree[node] |
| Extra data per node | Easy — add attributes to the class | Harder — need a second dict or tuple values |
| Best used when… | You need rich node data or recursive algorithms | You want a lightweight, quick-to-build tree |
Worked Example — Building & Traversing a Tree
Let's build a tree that represents a simple file system: a root folder home containing two folders docs and music. The docs folder contains essay.txt, and music contains song.mp3 and album. We will build this tree both ways and then print every node's name.
val and children attributes. class TreeNode:
def __init__(self, val):
self.val = val
self.children = []home = TreeNode("home") — this is our root. Then: docs = TreeNode("docs"), music = TreeNode("music"), essay = TreeNode("essay.txt"), song = TreeNode("song.mp3"), album = TreeNode("album"). Now link: home.children = [docs, music], docs.children = [essay], music.children = [song, album].home.def print_tree(node, indent=0):
print(" " * indent + node.val)
for child in node.children:
print_tree(child, indent + 1) Calling print_tree(home) visits every node.tree = {
"home": ["docs", "music"],
"docs": ["essay.txt"],
"music": ["song.mp3", "album"],
"essay.txt": [],
"song.mp3": [],
"album": []
} — one dictionary, no classes needed.def print_adj(tree, node, indent=0):
print(" " * indent + node)
for child in tree[node]:
print_adj(tree, child, indent + 1) Calling print_adj(tree, "home") produces the same output as Step 3.Strengths & Limitations
Neither representation is "better" in every situation. Your choice depends on the specific problem. The table below highlights the trade-offs so you can make an informed decision.
| Criterion | Node/Object ✅ / ⚠️ | Adjacency List ✅ / ⚠️ |
|---|---|---|
| Ease of setup | ⚠️ Requires writing a class and creating many objects | ✅ Just fill a dictionary — fast and simple |
| Storing extra data per node | ✅ Add attributes to the class (color, size, etc.) | ⚠️ Needs a second dictionary or more complex values |
| Recursive algorithms | ✅ Very natural — pass the node, recurse on children | ✅ Also works well — pass the key, recurse on children |
| Finding a node's parent | ⚠️ Must add a parent attribute manually | ⚠️ Must scan all keys or add a reverse mapping |
| Serialization (saving to file) | ⚠️ Objects must be converted to dicts/JSON first | ✅ Already a dictionary — converts to JSON directly |
| Memory usage | ⚠️ Slightly higher due to object overhead | ✅ Lighter — only dict keys and lists |
Connection to Advanced Data Structures
The two representations you learned here are the building blocks for a whole family of more specialized data structures. Once you are comfortable building and traversing a basic tree, you can extend these patterns to solve much more complex problems.
| Basic Concept | Advanced Extension | What Changes |
|---|---|---|
| General tree with children list | Binary Search Tree (BST) | Each node has at most 2 children (left < parent < right). Node class uses self.left and self.right. |
| Adjacency list dictionary | Graph adjacency list | Nodes can have cycles and multiple parents. The dictionary still works, but you add visited-tracking during traversal. |
| TreeNode with value attribute | Trie (prefix tree) | Each node stores a single character. Children are keyed by character, enabling fast word lookups. |
| Tree traversal (print all) | Heap / Priority Queue | A complete binary tree often stored as an array. Parent-child relationships are computed with index formulas instead of pointers. |
In AP Computer Science and college-level courses, you will encounter these structures frequently. The key insight is that every advanced tree structure is just a specialized version of the basic node-and-children pattern. Master the fundamentals now, and the advanced versions will feel much more approachable.
Practice Problems
tree = {"X": ["Y", "Z"], "Y": ["W"], "Z": ["V", "U"], "W": [], "V": [], "U": []}, write a Python function count_leaves(tree, node) that returns the number of leaf nodes in the subtree rooted at node. What does count_leaves(tree, "X") return?TreeNode class and build the tree). Then write a function that prints every course name.Lesson Summary
A tree is a hierarchical data structure made of nodes connected by edges, with a single root and no cycles. A tree with n nodes always has exactly n − 1 edges. You can represent a tree in Python using the node/object approach — where each node is a class instance storing a value and a list of child references — or the adjacency list approach — where a single dictionary maps each node to its children.
The node/object representation shines when you need rich per-node data or are implementing classic recursive algorithms. The adjacency list is ideal for lightweight, quick setups and easy serialization. Both use O(n) space and support the same traversal patterns. Mastering these two representations prepares you for advanced structures like binary search trees, tries, and heaps.