Trees and graphs, one node at a time

01

Tree or graph?

A graph is just dots (called nodes or vertices) joined by lines (called edges). That's it. Cities and roads, people and friendships, web pages and links.

A tree is a special graph with two rules: everything is connected, and there are no loops. Because of that, there is exactly one route between any two nodes, and a tree with n nodes always has n − 1 edges.

# A tree: each node lists its children
tree = {"A": ["B", "C"], "B": ["D", "E"], "C": ["F"]}

# A graph: each node lists its neighbours.
# The extra E-F link creates a loop (a cycle)
graph = {"A": ["B", "C"], "B": ["A", "D", "E"],
         "C": ["A", "F"], "D": ["B"],
         "E": ["B", "F"], "F": ["C", "E"]}

02

Parts of a tree

Trees borrow words from family trees. Click any node on the right and its relatives light up.

• Root: the single node at the top. It has no parent.
• Parent / child: a node directly above / below another.
• Leaf: a node with no children, at the bottom.
• Depth: how many steps down from the root.
• Height: the longest walk down from a node to a leaf.
• Subtree: a node plus everything below it. Every subtree is itself a tree.
• Binary tree: every node has at most 2 children, a left and a right.

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def height(node):
    if node is None:
        return -1          # so a leaf has height 0
    return 1 + max(height(node.left), height(node.right))

03

Walking a tree

A traversal means visiting every node once, in some order. The four classic orders differ only in when you write down the current node compared with its children.

• Preorder: me → left → right
• Inorder: left → me → right
• Postorder: left → right → me
• Level order: row by row, top to bottom

04

Binary search tree

A BST is a binary tree with one promise: everything on the left is smaller, everything on the right is bigger. That promise lets you throw away half the tree at every step when searching.

With 1,000,000 numbers in a balanced BST you need only about 20 comparisons to find one. But if you insert numbers already sorted, the tree becomes a long chain and search gets slow. Try the "sorted input" button to see why balanced trees (AVL, Red-Black) exist.

def insert(node, val):
    if node is None:
        return Node(val)
    if val < node.val:
        node.left = insert(node.left, val)
    else:
        node.right = insert(node.right, val)
    return node

def search(node, val):
    while node and node.val != val:
        node = node.left if val < node.val else node.right
    return node   # None means "not found"

05

Storing a graph

A computer can't see a picture, so we write the graph down. Two common ways:

• Adjacency list: for each node, a list of its neighbours. Small and fast to loop over. Used most of the time.
• Adjacency matrix: a grid where row A, column B says whether A and B are connected. Instant "are these two linked?" checks, but it uses V × V cells even when most are empty.

Edges can also carry a weight: a distance, a cost, a time. Tick "weighted" to see the same graph with numbers on it.

# Adjacency list
graph = {"A": ["B", "C"], "B": ["A", "C", "D"], ...}

# Weighted adjacency list
graph = {"A": [("B", 4), ("C", 2)], ...}

# Adjacency matrix (rows/cols = A..G)
M = [[0,1,1,0,0,0,0],
     [1,0,1,1,0,0,0], ...]
connected = M[0][1] == 1   # is A linked to B?

06

BFS vs DFS

Two ways to explore every node reachable from a start point. The only real difference is the waiting line you use.

• BFS (Breadth-First Search) uses a queue: first in, first out. It explores in rings: all neighbours, then neighbours of neighbours. It finds the route with the fewest hops.
• DFS (Depth-First Search) uses a stack (or recursion): last in, first out. It runs down one path as far as possible, then backs up and tries the next.

07

Shortest path (Dijkstra)

When edges have weights, fewest hops is not the same as cheapest route. A → C → B costs 2 + 1 = 3, cheaper than the direct A → B road of 4.

Dijkstra's algorithm keeps a best-known distance for every node. It repeatedly picks the closest node it hasn't finalised yet, locks it in, and checks whether going through it gives any neighbour a shorter route. Each improvement is called relaxing an edge.

It works only when no weight is negative. The blue numbers above nodes are the current best distances.

import heapq

def dijkstra(graph, start):
    dist = {n: float("inf") for n in graph}
    dist[start] = 0
    heap = [(0, start)]               # (distance, node)
    while heap:
        d, node = heapq.heappop(heap) # closest unfinished node
        if d > dist[node]:
            continue                  # old, stale entry
        for nb, w in graph[node]:
            if d + w < dist[nb]:      # found a shorter route
                dist[nb] = d + w
                heapq.heappush(heap, (dist[nb], nb))
    return dist