13.3. Trees & Graphs#
Trees and graphs organize relationships. Trees model hierarchy; graphs model general connections.
Outline
Trees
o Root, children, leaves
o Recursive traversal
Binary Trees
o Nodes and traversals
o Binary search trees
Graphs
o Nodes and edges
o Adjacency lists
Graph Traversal
o Breadth-first search
o Depth-first search
Summary
13.3.1. Trees#
A tree is a linked structure with a root and branches. Each node can have children. A node that has children is the parent of each of them, and each of those nodes is a child of that node. Every node except the root has exactly one parent, and the root has none. A node with no children is called a leaf.
Trees are useful for hierarchical data such as folders, organization charts, HTML documents, decision trees, and expression trees.
class TreeNode:
def __init__(self, value):
self.value = value
self.children = []
def add_child(self, child):
self.children.append(child)
root = TreeNode("company")
analytics = TreeNode("analytics")
operations = TreeNode("operations")
root.add_child(analytics)
root.add_child(operations)
analytics.add_child(TreeNode("alice"))
analytics.add_child(TreeNode("bob"))
operations.add_child(TreeNode("charlie"))
def print_tree(node, level=0):
indent = " " * level
print(indent + str(node.value))
for child in node.children:
print_tree(child, level + 1)
print_tree(root)
company
analytics
alice
bob
operations
charlie
### Exercise: Add a Tree Node
# Add a new employee named dana under operations.
# Then print the tree again.
### Your code starts here.
### Your code ends here.
company
analytics
alice
bob
operations
charlie
dana
13.3.2. Binary Trees#
A binary tree is a tree in which each node has at most two children, called the left child and the right child. Fixing the number of children at two makes the structure simple to code, and it is the basis of binary search trees, which keep values in sorted order.
13.3.2.1. Binary Tree Nodes#
A binary tree node stores a value and two links. Instead of the children list in TreeNode, each node has a left attribute and a right attribute. A link that points to no node is None.
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
The next cell builds this six-node tree by hand, one link at a time:
1
/ \
2 3
/ \ \
4 5 6
tree = Node(1)
tree.left = Node(2)
tree.right = Node(3)
tree.left.left = Node(4)
tree.left.right = Node(5)
tree.right.right = Node(6)
print(tree.value) # 1
print(tree.left.value, tree.right.value) # 2 3
print(tree.left.left.left, tree.left.left.right) # None None
1
2 3
None None
The terms from the Trees section carry over. Node 1 is the root. Nodes 4, 5, and 6 are leaves because both of their links are None. Node 3 has only a right child, which a binary tree allows.
The height of a tree is the number of levels on the longest path from the root down to a leaf. This tree has height 3, following the path 1, 2, 4. An empty tree has height 0.
Each link also points to a smaller binary tree, called a subtree. The left subtree of node 1 is the tree rooted at node 2. Because every subtree is itself a binary tree, recursive functions fit this structure naturally.
13.3.2.2. Traversals#
A tree traversal visits every node exactly once. In a binary tree, the three classic orders differ only in when you visit the node itself relative to its two subtrees:
Preorder: the node, then the left subtree, then the right subtree.
Inorder: the left subtree, then the node, then the right subtree.
Postorder: the left subtree, then the right subtree, then the node.
Each function below follows the recursive pattern from 4.3 Recursion. The base case is an empty tree (None), which contributes an empty list. The recursive case joins the node’s value with the lists returned for its two subtrees.
def preorder(node):
if node is None:
return []
return [node.value] + preorder(node.left) + preorder(node.right)
def inorder(node):
if node is None:
return []
return inorder(node.left) + [node.value] + inorder(node.right)
def postorder(node):
if node is None:
return []
return postorder(node.left) + postorder(node.right) + [node.value]
print(preorder(tree)) # [1, 2, 4, 5, 3, 6]
print(inorder(tree)) # [4, 2, 5, 1, 3, 6]
print(postorder(tree)) # [4, 5, 2, 6, 3, 1]
[1, 2, 4, 5, 3, 6]
[4, 2, 5, 1, 3, 6]
[4, 5, 2, 6, 3, 1]
The three functions differ only in where [node.value] goes, and each order suits a different job:
Preorder visits a parent before its children, so it fits copying or serializing a tree: rebuilding nodes in this order always creates each parent before its children.
Inorder visits everything on the left before the node and everything on the right after it, so on a binary search tree (next section) it returns the values in sorted order.
Postorder visits children before their parent, so it fits work that needs the children finished first, such as deleting a tree from the bottom up or evaluating an expression tree, where an operator needs both operand values.
13.3.2.3. Binary Search Trees#
A binary search tree (BST) is a binary tree that keeps one ordering rule at every node: all values in the left subtree are smaller than the node’s value, and all values in the right subtree are larger. The rule tells you which way to go at every step, so a search follows a single path from the root instead of visiting every node.
insert(root, value) adds a value and returns the root of the updated tree. If the tree is empty, the new node becomes the root. Otherwise, the function compares the value with the current node and inserts into the left or right subtree. This version ignores duplicates. contains(root, value) follows the same path with a loop, stopping when it finds the value or reaches None.
def insert(root, value):
if root is None:
return Node(value)
if value < root.value:
root.left = insert(root.left, value)
elif value > root.value:
root.right = insert(root.right, value)
return root
def contains(root, value):
node = root
while node is not None:
if value == node.value:
return True
if value < node.value:
node = node.left
else:
node = node.right
return False
bst = None
for num in [50, 30, 70, 20, 40, 60, 80]:
bst = insert(bst, num)
print(contains(bst, 60)) # True
print(contains(bst, 65)) # False
print(inorder(bst)) # [20, 30, 40, 50, 60, 70, 80]
True
False
[20, 30, 40, 50, 60, 70, 80]
The values went in unsorted, but inorder traversal returns them sorted. The ordering rule guarantees it: everything to the left of a node is smaller, and everything to the right is larger. The insertions build this tree:
50
/ \
30 70
/ \ / \
20 40 60 80
Searching for 60 checks 50, then 70, then 60: three steps for seven values, because the tree has height 3.
The shape of a BST depends on the order of insertion. The next cell inserts values that are already sorted and then walks down the right links, reporting whether each node has a left child.
chain = None
for num in [20, 30, 40, 50, 60]:
chain = insert(chain, num)
node = chain
while node is not None:
print(node.value, "has left child:", node.left is not None)
node = node.right
20 has left child: False
30 has left child: False
40 has left child: False
50 has left child: False
60 has left child: False
Each new value is larger than everything already in the tree, so it always goes to the right. The result is a degenerate tree: a chain in which every node has at most one child, and the height equals the number of nodes.
As 13.1 ADT Basics explains, BST lookup costs O(h), where h is the height. In the balanced tree bst, h grows like log n, so lookups stay fast as the tree grows. In chain, h = n, so contains(chain, 60) checks all five nodes, which is no better than scanning a list. Self-balancing trees avoid this by restructuring themselves as values are inserted.
### Exercise: Tree Height
# Write a function tree_height(node) that returns the number of levels in a binary tree.
# An empty tree (None) has height 0, and a single node has height 1.
# Then print the heights of tree, bst, and chain.
### Your code starts here.
### Your code ends here.
3
3
5
13.3.3. Graphs#
A graph stores relationships between items. The items are nodes. The relationships are edges.
A common Python representation is an adjacency list: a dictionary where each key maps to a list of neighbors.
graph = {
"alice": ["bob", "charlie"],
"bob": ["alice", "dana"],
"charlie": ["alice", "dana"],
"dana": ["bob", "charlie"],
}
print(graph["alice"])
['bob', 'charlie']
### Exercise: Add a Graph Edge
# Add a new person named erin who is connected to dana.
# Update both adjacency lists so the relationship works both ways.
# Then print graph["dana"].
### Your code starts here.
### Your code ends here.
['bob', 'charlie', 'erin']
13.3.4. Graph Traversal#
A traversal visits nodes systematically.
Breadth-first search uses a queue and explores nearby nodes first.
Depth-first search uses a stack or recursion and follows one path before backing up.
from collections import deque
def breadth_first_search(graph, start):
visited = set()
order = []
queue = deque([start])
while queue:
node = queue.popleft()
if node in visited:
continue
visited.add(node)
order.append(node)
for neighbor in graph.get(node, []):
if neighbor not in visited:
queue.append(neighbor)
return order
print(breadth_first_search(graph, "alice"))
['alice', 'bob', 'charlie', 'dana', 'erin']
### Exercise: Stop at a Target
# Modify breadth_first_search so it accepts a target node.
# The function should return the visited order once the target is found.
### Your code starts here.
### Your code ends here.
['alice', 'bob', 'charlie', 'dana', 'erin']
Depth-first search follows one path as far as possible before backing up. It uses a stack — either explicitly or via recursion.
def depth_first_search(graph, start):
visited = set()
order = []
stack = [start]
while stack:
node = stack.pop()
if node in visited:
continue
visited.add(node)
order.append(node)
for neighbor in graph.get(node, []):
if neighbor not in visited:
stack.append(neighbor)
return order
print(depth_first_search(graph, "alice"))
['alice', 'charlie', 'dana', 'erin', 'bob']
### Exercise: Compare Traversal Orders
# Call both breadth_first_search and depth_first_search on graph starting from "alice".
# Print both results and explain in a comment why the orders differ.
### Your code starts here.
### Your code ends here.
['alice', 'bob', 'charlie', 'dana', 'erin']
['alice', 'charlie', 'dana', 'erin', 'bob']
13.3.5. Summary#
Trees model hierarchy. Binary trees limit each node to two children, and binary search trees use an ordering rule so a lookup follows one path from the root. Graphs model general relationships. Traversal algorithms make these structures useful because they provide repeatable ways to visit connected data.