Trees and Graphs

A binary tree

class TreeNode:
    __slots__ = ("value", "left", "right")

    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

    def __repr__(self):
        return f"TreeNode({self.value!r})"


#         4
#       /   \
#      2     6
#     / \   / \
#    1   3 5   7
root = TreeNode(4,
                TreeNode(2, TreeNode(1), TreeNode(3)),
                TreeNode(6, TreeNode(5), TreeNode(7)))

Depth first traversal

def inorder(node):
    """Left, node, right. On a search tree this yields sorted order."""
    if node is None:
        return
    yield from inorder(node.left)
    yield node.value
    yield from inorder(node.right)


def preorder(node):
    """Node, left, right. Useful for copying a tree."""
    if node is None:
        return
    yield node.value
    yield from preorder(node.left)
    yield from preorder(node.right)


def postorder(node):
    """Left, right, node. Useful for deleting or evaluating."""
    if node is None:
        return
    yield from postorder(node.left)
    yield from postorder(node.right)
    yield node.value


print(list(inorder(root)))       # [1, 2, 3, 4, 5, 6, 7]
print(list(preorder(root)))      # [4, 2, 1, 3, 6, 5, 7]
print(list(postorder(root)))     # [1, 3, 2, 5, 7, 6, 4]

The three differ only in where the node is visited relative to its children. Choosing the right one usually solves half the problem.

Without recursion

def inorder_iterative(root):
    """The same order, using an explicit stack. No recursion limit."""
    result, stack, current = [], [], root

    while stack or current:
        while current:                    # go as far left as possible
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.value)
        current = current.right           # then handle the right subtree

    return result


print(inorder_iterative(root))

Breadth first traversal

from collections import deque


def level_order(root):
    """Visit every node level by level, using a queue."""
    if root is None:
        return []

    result, queue = [], deque([root])
    while queue:
        node = queue.popleft()
        result.append(node.value)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

    return result


def levels(root):
    """Group the values by depth."""
    if root is None:
        return []

    result, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):       # exactly one level's worth
            node = queue.popleft()
            level.append(node.value)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)

    return result


print(level_order(root))     # [4, 2, 6, 1, 3, 5, 7]
print(levels(root))          # [[4], [2, 6], [1, 3, 5, 7]]

The only difference between depth first and breadth first is the container: a stack goes deep, a queue goes wide. Everything else about the two loops is identical.

Common tree operations

def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))


def count_nodes(node):
    if node is None:
        return 0
    return 1 + count_nodes(node.left) + count_nodes(node.right)


def count_leaves(node):
    if node is None:
        return 0
    if node.left is None and node.right is None:
        return 1
    return count_leaves(node.left) + count_leaves(node.right)


def is_balanced(node):
    """No subtree differs in height by more than one."""
    def check(n):
        if n is None:
            return 0
        left = check(n.left)
        right = check(n.right)
        if left < 0 or right < 0 or abs(left - right) > 1:
            return -1
        return 1 + max(left, right)

    return check(node) >= 0


def mirror(node):
    """Swap every left and right child."""
    if node is None:
        return None
    return TreeNode(node.value, mirror(node.right), mirror(node.left))


print(height(root), count_nodes(root), count_leaves(root), is_balanced(root))
print(list(inorder(mirror(root))))

Binary search tree

class BST:
    """Left subtree is smaller, right subtree is larger."""

    def __init__(self):
        self.root = None
        self._size = 0

    def insert(self, value):
        self.root = self._insert(self.root, value)
        return self

    def _insert(self, node, value):
        if node is None:
            self._size += 1
            return TreeNode(value)
        if value < node.value:
            node.left = self._insert(node.left, value)
        elif value > node.value:
            node.right = self._insert(node.right, value)
        return node                       # equal values are ignored

    def __contains__(self, value):
        node = self.root
        while node:
            if value == node.value:
                return True
            node = node.left if value < node.value else node.right
        return False

    def minimum(self):
        node = self.root
        while node and node.left:
            node = node.left
        return node.value if node else None

    def __iter__(self):
        yield from inorder(self.root)

    def __len__(self):
        return self._size


tree = BST()
for value in [4, 2, 6, 1, 3, 5, 7, 4]:
    tree.insert(value)

print(list(tree))          # [1, 2, 3, 4, 5, 6, 7] - sorted, duplicates ignored
print(5 in tree, 9 in tree)
print(tree.minimum(), len(tree))

def is_valid_bst(node, low=float("-inf"), high=float("inf")):
    """Every value must fit the range inherited from its ancestors."""
    if node is None:
        return True
    if not low < node.value < high:
        return False
    return (is_valid_bst(node.left, low, node.value)
            and is_valid_bst(node.right, node.value, high))


print(is_valid_bst(root))                                    # True
print(is_valid_bst(TreeNode(4, TreeNode(2, right=TreeNode(9)))))    # False

A search tree gives O(log n) lookup only while it stays balanced. Inserting sorted data produces a tree that is effectively a linked list, and every operation becomes O(n). In Python a dict gives O(1) lookup with no balancing to worry about, so build a BST to understand it rather than to use it.

Graphs

from collections import defaultdict, deque


class Graph:
    """An adjacency list: each node maps to the nodes it connects to."""

    def __init__(self, directed=False):
        self.edges = defaultdict(set)
        self.directed = directed

    def add_edge(self, a, b):
        self.edges[a].add(b)
        if not self.directed:
            self.edges[b].add(a)
        return self

    def neighbours(self, node):
        return sorted(self.edges[node])

    def nodes(self):
        found = set(self.edges)
        for targets in self.edges.values():
            found |= targets
        return sorted(found)


graph = Graph()
for a, b in [("A", "B"), ("A", "C"), ("B", "D"), ("C", "D"), ("D", "E")]:
    graph.add_edge(a, b)

print(graph.nodes())
print(graph.neighbours("D"))

      A
     / \
    B   C
     \ /
      D
      |
      E

Graph traversal

from collections import deque


def bfs(graph, start):
    """Breadth first: nearest nodes first. Uses a QUEUE."""
    visited = {start}
    order = []
    queue = deque([start])

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbour in graph.neighbours(node):
            if neighbour not in visited:
                visited.add(neighbour)         # mark on ENQUEUE, not on visit
                queue.append(neighbour)

    return order


def dfs(graph, start):
    """Depth first: follow one path as far as it goes. Uses a STACK."""
    visited = set()
    order = []
    stack = [start]

    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        for neighbour in reversed(graph.neighbours(node)):
            if neighbour not in visited:
                stack.append(neighbour)

    return order


def dfs_recursive(graph, node, visited=None, order=None):
    visited = set() if visited is None else visited
    order = [] if order is None else order

    visited.add(node)
    order.append(node)
    for neighbour in graph.neighbours(node):
        if neighbour not in visited:
            dfs_recursive(graph, neighbour, visited, order)

    return order


print(bfs(graph, "A"))             # ['A', 'B', 'C', 'D', 'E']
print(dfs(graph, "A"))             # ['A', 'B', 'D', 'C', 'E']
print(dfs_recursive(graph, "A"))

Marking a node as visited when it is enqueued, not when it is dequeued, is essential. Otherwise a node reachable by two paths is added to the queue twice.

Shortest path

from collections import deque


def shortest_path(graph, start, goal):
    """BFS finds the fewest edges, because it explores by distance."""
    if start == goal:
        return [start]

    previous = {start: None}
    queue = deque([start])

    while queue:
        node = queue.popleft()
        for neighbour in graph.neighbours(node):
            if neighbour in previous:
                continue
            previous[neighbour] = node
            if neighbour == goal:
                path = [goal]
                while previous[path[-1]] is not None:
                    path.append(previous[path[-1]])
                return path[::-1]
            queue.append(neighbour)

    return None


print(shortest_path(graph, "A", "E"))     # ['A', 'B', 'D', 'E'] - 3 edges
print(shortest_path(graph, "B", "C"))

import heapq
from collections import defaultdict


def dijkstra(weighted, start):
    """Shortest distances when edges have different costs."""
    distances = {start: 0}
    visited = set()
    queue = [(0, start)]

    while queue:
        distance, node = heapq.heappop(queue)
        if node in visited:
            continue
        visited.add(node)

        for neighbour, weight in weighted.get(node, {}).items():
            candidate = distance + weight
            if candidate < distances.get(neighbour, float("inf")):
                distances[neighbour] = candidate
                heapq.heappush(queue, (candidate, neighbour))

    return distances


weighted = {
    "A": {"B": 4, "C": 2},
    "B": {"D": 5},
    "C": {"B": 1, "D": 8},
    "D": {"E": 3},
}

print(dijkstra(weighted, "A"))     # {'A': 0, 'C': 2, 'B': 3, 'D': 8, 'E': 11}

BFS assumes every edge costs the same. When they differ, a priority queue replaces the plain queue and the algorithm becomes Dijkstra's - the same walk, always expanding the cheapest known node next.

Cycles and ordering

def has_cycle_undirected(graph):
    visited = set()

    def visit(node, parent):
        visited.add(node)
        for neighbour in graph.neighbours(node):
            if neighbour not in visited:
                if visit(neighbour, node):
                    return True
            elif neighbour != parent:        # a visited node that is not our parent
                return True
        return False

    return any(visit(n, None) for n in graph.nodes() if n not in visited)


print(has_cycle_undirected(graph))      # True: A-B-D-C-A

from collections import defaultdict, deque


def topological_order(dependencies):
    """Order tasks so every dependency comes first. Detects cycles."""
    graph = defaultdict(set)
    incoming = defaultdict(int)
    tasks = set()

    for task, needs in dependencies.items():
        tasks.add(task)
        for need in needs:
            tasks.add(need)
            if task not in graph[need]:
                graph[need].add(task)
                incoming[task] += 1

    queue = deque(sorted(t for t in tasks if incoming[t] == 0))
    order = []

    while queue:
        task = queue.popleft()
        order.append(task)
        for dependent in sorted(graph[task]):
            incoming[dependent] -= 1
            if incoming[dependent] == 0:
                queue.append(dependent)

    if len(order) != len(tasks):
        raise ValueError("the dependencies contain a cycle")

    return order


build = {
    "test": ["compile"],
    "compile": ["fetch"],
    "package": ["test", "docs"],
    "docs": ["fetch"],
    "fetch": [],
}

print(topological_order(build))

Grids as graphs

from collections import deque


def count_islands(grid):
    """Count connected regions of 1s. Every grid problem is a graph problem."""
    if not grid:
        return 0

    rows, columns = len(grid), len(grid[0])
    visited = set()
    islands = 0

    for r in range(rows):
        for c in range(columns):
            if grid[r][c] != 1 or (r, c) in visited:
                continue

            islands += 1
            queue = deque([(r, c)])
            visited.add((r, c))

            while queue:
                row, column = queue.popleft()
                for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                    nr, nc = row + dr, column + dc
                    if (0 <= nr < rows and 0 <= nc < columns
                            and grid[nr][nc] == 1 and (nr, nc) not in visited):
                        visited.add((nr, nc))
                        queue.append((nr, nc))

    return islands


grid = [
    [1, 1, 0, 0],
    [1, 0, 0, 1],
    [0, 0, 1, 1],
]
print(count_islands(grid))     # 2

Choosing a traversal

Common mistakes

• Forgetting the visited set, so a cycle loops forever.
• Marking a node visited when dequeued rather than when enqueued, adding duplicates.
• Using a list as a queue, making BFS O(n²).
• Recursing deeply enough to hit the recursion limit; use an explicit stack.
• Assuming BFS gives the shortest path when edges have different weights.
• Inserting sorted data into a BST and losing the O(log n) behaviour.
• Not checking grid boundaries before indexing.

Best practices

• Use deque for BFS and a list or recursion for DFS.
• Track visited nodes in a set.
• Store a graph as a dictionary of adjacency sets.
• Use heapq the moment edges have weights.
• Convert grid problems into graph problems by treating each cell as a node.
• Use recursion for trees and an explicit stack when depth could be large.

Practice

1. Write all three depth first traversals, once recursively and once iteratively.
2. Find the lowest common ancestor of two nodes in a binary search tree.
3. Determine whether a graph is connected.
4. Find every path between two nodes using DFS with backtracking.
5. Solve a maze given as a grid of walls and open cells, returning the shortest route.

Conclusion

A tree is a graph without cycles. Depth first uses a stack and goes deep; breadth first uses a queue and finds the fewest edges. Keep a visited set, choose the container to match the question, and remember that grids and dependency lists are graphs too.