Trees & Graphs

14.3. Trees & Graphs#

Trees and graphs organize relationships. Trees model hierarchy; graphs model general connections.

Outline

Trees
  o Root, children, leaves
  o Recursive traversal
Graphs
  o Nodes and edges
  o Adjacency lists
Graph Traversal
  o Breadth-first search
  o Depth-first search
Summary

14.3.1. Trees#

A tree is a linked structure with a root and branches. Each node can have children. 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.

Hide code cell source

 
### Solution
operations.add_child(TreeNode("dana"))
print_tree(root)

company
  analytics
    alice
    bob
  operations
    charlie
    dana

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

Hide code cell source

 
### Solution
graph["erin"] = ["dana"]
graph["dana"].append("erin")

print(graph["dana"])

['bob', 'charlie', 'erin']

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

Hide code cell source

 
### Solution
def bfs_until(graph, start, target):
    visited = set()
    order = []
    queue = deque([start])

    while queue:
        node = queue.popleft()
        if node in visited:
            continue

        visited.add(node)
        order.append(node)

        if node == target:
            return order

        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                queue.append(neighbor)

    return order


print(bfs_until(graph, "alice", "erin"))

['alice', 'bob', 'charlie', 'dana', 'erin']

14.3.4. Summary#

Trees model hierarchy. Graphs model general relationships. Traversal algorithms make these structures useful because they provide repeatable ways to visit connected data.

Contents