Stop 20 · Data Structures & AlgorithmsTopics · 3/8

Trees & Graphs

In short

Folders on your laptop, a decision tree model, the links between people on LinkedIn: all trees and graphs. Interviewers use them to see if you can walk a structure without getting lost.

Hierarchical and networked data structures — core to interview problems and directly relevant to real structures like model architectures and knowledge graphs.

The purple blob pins photos of relatives onto a family tree drawn on a wall, with strings linking some sideways.

Think of it like this

The family tree at a wedding

At a big Indian wedding, aunties explain everyone with a family tree: Dadaji at the top, then his children, then grandchildren. That's a tree, every person has one parent line. Then you learn your cousin's friend is also your neighbour's nephew. Once links go sideways and loop around, it's a graph.

Watch it happen

Breadth-first: one generation at a time

Dadaji

Papa

Chacha

You

Didi

Cousin

1/4BFS starts at the root and puts it in a queue. Level 0 is just Dadaji.

The big ideas

What you need to know

A tree is a graph without loops

One root, every node has exactly one parent. Graphs allow any links, including cycles.

Store graphs as adjacency lists

A dict from each node to its neighbours. Compact, and easy to loop over.

BFS for shortest hops

BFS uses a queue and visits level by level, so it finds the fewest-hops path in an unweighted graph.

DFS for exploring everything

DFS goes deep with recursion or a stack. Good for cycles, connected parts and tree depth.

See it in code

Walk through the code

python

1from collections import deque2 3graph = {"A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D"], "D": ["B", "C", "E"], "E": ["D"]}4def bfs(start):5    visited, order = {start}, []6    queue = deque([start])7    while queue:8        node = queue.popleft()9        order.append(node)10        for nxt in graph[node]:11            if nxt not in visited:12                visited.add(nxt)13                queue.append(nxt)14    return order15 16print(bfs("A"))  # ['A', 'B', 'C', 'D', 'E']

1/4The graph as a dict: each node maps to the list of its neighbours.

BFS on an adjacency list touches each node and edge once, so it runs in O(V + E). The visited set stops it looping between A and B forever.

Save yourself the pain

Common mistakes

Oops

Forgetting the visited set on a graph because the tree version didn't need one.

Do this instead

Trees can't loop, graphs can. Always track visited nodes in a graph, or you'll circle A to B to A forever.

Oops

Using a Python list and list.pop(0) as the BFS queue.

Do this instead

pop(0) shifts the whole list each time. Use collections.deque and popleft(), which is O(1).

Your mission

Walk three structures

~45 min

Quick check

You need the fewest connections between two people in a friend network. Which traversal fits?

Go deeper

1Practice DFS and BFS traversal on both trees and graphs until they're automatic.
2Solve tree problems: depth, balance, path sum, lowest common ancestor.
3Solve graph problems: connected components, shortest path, cycle detection.