Bäume und Graphen visualisiert

Data With Relationships

So far, we've looked at data in lines - arrays, linked lists, stacks, and queues all arrange items in a sequence. But the real world isn't linear. Family trees branch out. Social networks form webs. Road maps create interconnected routes.

Trees and graphs capture these relationships, and they're at the heart of some of AI's most powerful techniques.

Trees - Hierarchical Data

A tree is a structure where each item (called a node) can have child nodes, forming a hierarchy. There's one special node at the top called the root, and nodes with no children are called leaves.

         CEO
        /    \
      CTO    CFO
     /   \      \
   Dev1  Dev2   Accountant

Trees Are Everywhere

• File systems: Folders contain subfolders which contain files - a tree.
• HTML/DOM: Every web page is a tree of nested elements.
• Organisation charts: Managers have reports who may have their own reports.
• JSON data: The nested structure of JSON is fundamentally a tree.

Binary Trees

A binary tree restricts each node to at most two children - a left child and a right child. This simple constraint enables powerful algorithms.

        8
       / \
      3   10
     / \    \
    1   6    14

Binary Search Trees (BSTs)

A binary search tree adds one rule: for every node, all values in the left subtree are smaller, and all values in the right subtree are larger.

This makes searching fast - at each node, you know whether to go left or right:

Find 6 in the BST above:
  Start at 8 → 6 < 8, go left
  At 3 → 6 > 3, go right
  At 6 → Found it!

Time complexity: O(log n) for a balanced tree - the same logarithmic magic as binary search on a sorted array.

Graphs - Everything Connected

A graph generalises trees by removing the hierarchy constraint. It consists of nodes (also called vertices) and edges (connections between nodes). Edges can be:

• Directed (one-way: A → B) or undirected (two-way: A ↔ B)
• Weighted (each edge has a cost/distance) or unweighted

Social network (undirected):
  Alice - Bob - Charlie
    \       |
     Diana - Eve

Road map (weighted, directed):
  London →(2h)→ Birmingham →(1.5h)→ Manchester

Graphs Are Everywhere

• Social networks: People are nodes; friendships are edges.
• The internet: Web pages are nodes; hyperlinks are edges.
• Road maps: Intersections are nodes; roads are edges with distance weights.
• Recommendation systems: Users and products are nodes; interactions are edges.

How AI Uses Trees

Decision Trees

One of the most interpretable AI models is the decision tree. It asks a series of yes/no questions to classify data:

Is temperature > 30°C?
├── Yes: Is humidity > 70%?
│   ├── Yes: "Don't play tennis"
│   └── No: "Play tennis"
└── No: Is it windy?
    ├── Yes: "Don't play tennis"
    └── No: "Play tennis"

Decision trees are popular because humans can read and understand them - crucial in healthcare, finance, and legal AI where explainability matters.

Random Forests

A random forest builds hundreds of decision trees, each trained on a slightly different subset of the data, then takes a vote. This ensemble approach is more accurate and robust than a single tree - and it's still one of the most widely used AI techniques in industry.

How AI Uses Graphs

Knowledge Graphs

A knowledge graph stores facts as relationships between entities:

(London) --[capital_of]--> (United Kingdom)
(London) --[located_in]--> (England)
(Big Ben) --[located_in]--> (London)

Google's Knowledge Graph powers those information panels you see in search results. When you search "Big Ben," the graph connects it to London, the UK, and related landmarks.

Recommendation Graphs

Netflix, Spotify, and Amazon model users and items as a graph. If users A and B both liked items X and Y, and user A also liked item Z, the graph suggests Z to user B. This is collaborative filtering powered by graph structure.

Traversal - Walking Through Trees and Graphs

Depth-First Search (DFS)

DFS explores as far as possible along one path before backtracking. Think of it as exploring a maze by always taking the leftmost turn until you hit a dead end, then backtracking.

        A
       / \
      B   C
     / \   \
    D   E   F

DFS order: A → B → D → E → C → F

DFS uses a stack (naturally via recursion, or explicitly). It's great for:

• Solving mazes and puzzles
• Detecting cycles in graphs
• Topological sorting (ordering tasks with dependencies)

Breadth-First Search (BFS)

BFS explores all neighbours at the current depth before moving deeper. Think of it as ripples spreading outward from a stone dropped in a pond.

        A
       / \
      B   C
     / \   \
    D   E   F

BFS order: A → B → C → D → E → F

BFS uses a queue. It's great for:

• Finding the shortest path in an unweighted graph
• Social network analysis (degrees of separation)
• Web crawling (visiting pages level by level)

Key Takeaways

• Trees model hierarchical data - file systems, HTML, and AI decision trees all use tree structures.
• Binary search trees enable O(log n) lookups by maintaining a sorted hierarchy.
• Graphs model interconnected data - social networks, knowledge bases, and recommendation engines.
• DFS (stack-based) goes deep; BFS (queue-based) goes wide - both power core AI algorithms like PageRank and recommendation engines.