Tree Representation — Represent a tree using nodes/objects or adjacency lists (conceptual) - Python

SECTION 1

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.

1847 • Cayley's Tree Graphs

Mathematician Arthur Cayley published work on tree-like graph structures, providing the first formal mathematical treatment of trees.

1956 • Binary Search Trees Formalized

Computer scientists introduced the binary search tree as a method for efficient data lookup, making trees central to algorithm design.

1972 • Unix File System

The Unix operating system used a tree structure for its directory hierarchy, proving that trees are ideal for organizing files and folders.

1998 • DOM Tree in Web Browsers

The W3C standardized the Document Object Model (DOM), representing every web page as a tree of HTML elements — a structure you interact with every time you browse the web.

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.

SECTION 2

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)

A single element in the tree that holds a value (data). Each node may have zero or more children.

Edge

A connection between a parent node and a child node. A tree with n nodes always has exactly n − 1 edges.

Root

The topmost node with no parent. Every tree has exactly one root, and all other nodes descend from it.

Node/Object Representation

Each node is a Python object (or class instance) that stores a value and references to its children. This mirrors the tree's structure directly in memory.

Adjacency List Representation

A dictionary (or list of lists) where each key is a node and its value is a list of that node's children. Compact and flexible for any tree shape.

✦

KEY TAKEAWAY

Think of a tree like a company's organizational chart. The CEO sits at the root, managers branch below, and individual employees are the leaves. A node/object representation is like giving each person their own business card that lists who they report to and who reports to them. An adjacency list is like a single spreadsheet where each row shows an employee and the names of their direct reports. Both describe the same hierarchy — they just store the information differently.

SECTION 3

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.

Each 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.

SECTION 4

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:

💡

General Tree Node

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.

💡

Adjacency List 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"].

TREE PROPERTY

edges = n − 1

A tree with n nodes always has exactly n − 1 edges. In an adjacency list, the total number of items across all value-lists equals n − 1.

SPACE COMPLEXITY

Space = O(n)

Both representations use space proportional to the number of nodes n. The node/object approach stores n objects; the adjacency list stores n keys plus n − 1 child entries.

SECTION 5

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.

Left: the node/object approach uses five linked 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

Quick comparison of the two tree representations

SECTION 6

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.

Building a File-System Tree in Python

1
Step 1 — Define the TreeNode class

Create a class with val and children attributes. class TreeNode: def __init__(self, val): self.val = val self.children = []

TreeNode class is ready.
2
Step 2 — Create node objects and link them

Instantiate each node, then append children to their parent's list. 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].

Six nodes linked as a tree rooted at home.
3
Step 3 — Traverse with a recursive function

Write a function that prints a node's value, then calls itself on each child. 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.

Output: home → docs → essay.txt → music → song.mp3 → album (each indented by depth).
4
Step 4 — Build the same tree as an adjacency list

tree = { "home": ["docs", "music"], "docs": ["essay.txt"], "music": ["song.mp3", "album"], "essay.txt": [], "song.mp3": [], "album": [] } — one dictionary, no classes needed.

Same tree, stored in a single dictionary.
5
Step 5 — Traverse the adjacency list recursively

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.

Both representations produce identical traversal output, confirming they encode the same tree.

SECTION 7

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

Trade-off summary between the two representations

🔑

WHEN TO USE WHICH

Use node objects when you need rich, per-node data or plan to implement classic algorithms like tree rotations or heap operations. Use an adjacency list when you want a quick, lightweight setup — for example, when reading tree data from a file or solving a contest-style problem where speed of coding matters.

SECTION 8

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.

How basic tree representation connects to advanced structures

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.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Explain in your own words the difference between representing a tree with node objects and representing it with an adjacency list. When might you prefer one over the other?

Show answer

In the node/object approach, each node is a separate Python object with a value and a list of references to its children. In the adjacency list approach, a single dictionary maps each node's value to a list of its children's values. You might prefer node objects when you need to store extra data on each node (like color or weight) by adding class attributes. You might prefer an adjacency list when you want a quick, lightweight setup — for example, when reading tree data from input and you only need to know the connections.

Question 2: BASIC CALCULATION

A tree has 8 nodes. How many edges does it have? Write a Python adjacency list (dictionary) for a tree where node 1 is the root with children 2 and 3, node 2 has child 4, node 3 has children 5, 6, and 7, and node 5 has child 8.

Show answer

A tree with 8 nodes has exactly 8 − 1 = 7 edges. The adjacency list is: tree = {1: [2, 3], 2: [4], 3: [5, 6, 7], 4: [], 5: [8], 6: [], 7: [], 8: []}. You can verify the 7 edges by counting all values across the lists: [2,3] has 2, [4] has 1, [5,6,7] has 3, and [8] has 1, totaling 2 + 1 + 3 + 1 = 7 edges.

Question 3: INTERMEDIATE

Given this adjacency list: 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?

Show answer

The function checks whether the current node has children. If it has none, it is a leaf and returns 1. Otherwise, it recursively counts leaves in each child's subtree and sums the results:

def count_leaves(tree, node):
    if not tree[node]:
        return 1
    return sum(count_leaves(tree, c) for c in tree[node])

. Calling count_leaves(tree, "X") returns 3, because the leaves are W, V, and U. The recursion visits X → Y → W (leaf, 1), then X → Z → V (leaf, 1) and Z → U (leaf, 1), summing to 3.

Question 4: APPLIED

You are building a simple course prerequisite system. "Intro CS" is the root. It leads to "Data Structures" and "Web Dev". "Data Structures" leads to "Algorithms" and "Databases". "Web Dev" leads to "Full Stack". Represent this as a tree using the node/object approach (write the Python code to create the TreeNode class and build the tree). Then write a function that prints every course name.

Show answer

First, define the class:

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.children = []

. Then build the tree:

intro = TreeNode("Intro CS")
ds = TreeNode("Data Structures")
web = TreeNode("Web Dev")
algo = TreeNode("Algorithms")
db = TreeNode("Databases")
fs = TreeNode("Full Stack")
intro.children = [ds, web]
ds.children = [algo, db]
web.children = [fs]

. Finally, a traversal function:

def print_courses(node):
    print(node.val)
    for child in node.children:
        print_courses(child)

. Calling print_courses(intro) prints all six courses in pre-order (parent before children).

Question 5: CRITICAL THINKING

Suppose you are given a tree as an adjacency list and you need to quickly find the parent of any given node. The basic adjacency list only stores children. Design a strategy (describe in words and pseudocode or Python) to build a parent lookup from the adjacency list. What is the time complexity of building this lookup, and what is the time complexity of a single parent query afterward?

Show answer

Iterate through every key-value pair in the adjacency list. For each parent node and each child in its children list, record the parent in a new dictionary:

def build_parent_map(tree):
    parent = {}
    for p, children in tree.items():
        for c in children:
            parent[c] = p
    return parent

. The root node will not appear as a value in this dictionary, which is correct because the root has no parent. Building the lookup visits every edge once, so it runs in O(n) time where n is the number of nodes (recall there are n − 1 edges). After building, each parent query is a single dictionary lookup, which is O(1) average time. This approach trades O(n) extra space for constant-time parent queries — a classic space-time trade-off.

SUMMARY

Lesson Summary

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.