Trees and Graphs Visualised

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.