Trees & Graphs — How AI Makes Decisions

Trees and graphs are everywhere in AI: decision trees classify data, knowledge graphs store relationships, and neural networks are directed acyclic graphs. Mastering traversal is non-negotiable.

Binary Tree Traversals

Every tree problem boils down to: how do you visit every node?

Binary tree showing BFS level-order vs DFS pre-order traversal with numbered visit sequence — BFS visits level by level (using a queue). DFS dives deep first (using a stack/recursion). Same tree, different visit orders.

BFS — Level Order (Queue)

from collections import deque

def level_order(root):
    if not root:
        return []
    result, queue = [], deque([root])

    while queue:
        level = []
        for _ in range(len(queue)):   # process one level
            node = queue.popleft()
            level.append(node.val)
            if node.left:  queue.append(node.left)
            if node.right: queue.append(node.right)
        result.append(level)

    return result

DFS — Three Flavours (Stack/Recursion)

def preorder(node):    # Root -> Left -> Right
    if not node: return
    visit(node)
    preorder(node.left)
    preorder(node.right)

def inorder(node):     # Left -> Root -> Right (sorted for BST!)
    if not node: return
    inorder(node.left)
    visit(node)
    inorder(node.right)

def postorder(node):   # Left -> Right -> Root (delete safely)
    if not node: return
    postorder(node.left)
    postorder(node.right)
    visit(node)

💡

When to use which? BFS for shortest path / level-by-level processing. DFS for path finding, depth calculation, or when you need to process children before parents (postorder).

Classic tree problems

| Problem | Traversal | Key Insight | |---------|-----------|-------------| | Max depth | DFS | 1 + max(depth(left), depth(right)) | | Level order traversal | BFS | Queue with level-size batching | | Validate BST | Inorder DFS | Values must be strictly increasing | | Lowest Common Ancestor | DFS | Recurse, check left/right returns | | Serialize/Deserialize | BFS or Preorder | Encode nulls as markers |

Graph Traversals

Graphs are trees without the "no cycles" guarantee. The key addition: a visited set to avoid infinite loops.

Graph with 9 nodes showing BFS wavefront expansion vs DFS deep-first exploration — BFS explores in expanding wavefronts (shortest distance guaranteed). DFS plunges down one path before backtracking.

Graph BFS

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])

    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

Graph DFS

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)

    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

🤔

Think about it:

Why is BFS guaranteed to find the shortest path in an unweighted graph? Because it explores all nodes at distance d before any node at distance d+1. DFS has no such guarantee — it might find a longer path first.

Classic graph problems

| Problem | Algorithm | Complexity | |---------|-----------|------------| | Shortest path (unweighted) | BFS | O(V + E) | | Detect cycle (undirected) | DFS with parent tracking | O(V + E) | | Detect cycle (directed) | DFS with 3-color marking | O(V + E) | | Number of islands | BFS/DFS flood fill | O(rows * cols) | | Topological sort | DFS postorder reverse | O(V + E) | | Connected components | BFS/DFS from each unvisited | O(V + E) |

AI Connection: Trees & Graphs in ML

🤯

Trees and graphs aren't just data structures — they're the backbone of modern AI:

Decision Trees & Random Forests: Each prediction walks a binary tree from root to leaf. Traversal order = feature importance ranking.
Knowledge Graphs: Google's Knowledge Graph, Wikidata, and enterprise ontologies are massive directed graphs traversed with BFS/DFS to answer questions.
Graph Neural Networks (GNNs): Message passing in GNNs is literally BFS — each node aggregates features from its k-hop neighbourhood.
Abstract Syntax Trees: LLMs that write code (Copilot, Codex) parse and generate ASTs — tree structures representing code.
Neural Network DAGs: A neural network is a directed acyclic graph. Backpropagation is reverse postorder DFS through the computation graph.

Quick Reference

| Structure | Traversal | Data Structure | Space | Best For | |-----------|-----------|----------------|-------|----------| | Tree BFS | Level order | Queue | O(w) | Level processing, shortest path | | Tree DFS | Pre/In/Post | Stack/Recursion | O(h) | Path problems, BST validation | | Graph BFS | Wavefront | Queue + Visited | O(V) | Shortest path, connected components | | Graph DFS | Deep first | Stack + Visited | O(V) | Cycle detection, topological sort |

w = max width, h = height, V = vertices

Lesson 2 of 30 of 3 completed

←Two Pointers & Sliding Window — How AI Scans Data Stacks & Queues — How AI Processes Sequences→