Trees and graphs in Python are the data structures behind almost everything that has a shape you can draw with dots and lines: a folder tree, a family tree, a social network, a map of roads, the import graph of your own project. This post builds them from scratch with plain classes and dictionaries, then runs breadth-first search (BFS) and depth-first search (DFS) so you can watch the two most important graph algorithms actually move through the data.

“Show me your flowcharts and conceal your tables, and I shall continue to be mystified. Show me your tables, and I won’t usually need your flowcharts; they’ll be obvious.”

Fred Brooks, The Mythical Man-Month

Last Updated: July 2026 | Tested on: Python 3.14.6 | Difficulty: Advanced | Reading Time: 19 minutes

Here is the everyday version. Think about the folders on your laptop. One top folder holds a few folders, each of those holds more folders and files, and nothing ever loops back on itself. That branching, no-loops shape is a tree. Now think about a group chat where anyone can add anyone: Aditi knows Anvi, Anvi knows Aviraj, Aviraj knows Rohan, and connections can circle back. That web, where loops are allowed and there is no single top, is a graph. A tree is really just a graph with strict rules. Once you see them that way, the same two search moves, going wide or going deep, solve a surprising number of real problems.

What Trees and Graphs Actually Are

Both structures are made of nodes (the dots) connected by edges (the lines). The difference is entirely about the rules those edges follow. A tree has exactly one root, every other node has exactly one parent, and there are no cycles, so there is always exactly one path between any two nodes. A graph drops all of that: any node can connect to any other, edges can be one-way or two-way, and loops are fine. That freedom is what lets a graph model messy real things like friendships or flight routes, while a tree models clean hierarchies like an org chart or a JSON document.

Binary Trees and the Four Traversals

A binary tree is the simplest useful tree: every node has at most two children, a left and a right. The interesting question is how you visit every node, because the order you choose changes what the visit is good for. Think of reading a book of nested chapters. You could announce each chapter title the moment you open it, or only once you have finished everything inside it. Those are different traversal orders, and each has a job.

There are four you should know. Preorder visits the node first, then its left subtree, then its right, which is how you copy or serialize a tree. Inorder visits left, then the node, then right, which on a search tree spits the values out in sorted order. Postorder visits both children before the node, which is how you delete a tree or compute a folder’s total size. Level order reads the tree top to bottom, one row at a time, using a queue. Let’s build one small tree and run all four.

📄 tree_traverse.py: build a binary tree and visit it four ways

from collections import deque

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

# Build this tree by hand:
#          4
#        /   \
#       2     6
#      / \   / \
#     1   3 5   7
root = Node(4,
            Node(2, Node(1), Node(3)),
            Node(6, Node(5), Node(7)))

def preorder(node):
    if node is None:
        return []
    return [node.value] + preorder(node.left) + preorder(node.right)

def inorder(node):
    if node is None:
        return []
    return inorder(node.left) + [node.value] + inorder(node.right)

def postorder(node):
    if node is None:
        return []
    return postorder(node.left) + postorder(node.right) + [node.value]

def level_order(node):
    result, queue = [], deque([node])
    while queue:
        current = queue.popleft()
        result.append(current.value)
        if current.left:
            queue.append(current.left)
        if current.right:
            queue.append(current.right)
    return result

print("Preorder   (root, left, right):", preorder(root))
print("Inorder    (left, root, right):", inorder(root))
print("Postorder  (left, right, root):", postorder(root))
print("Level order (top to bottom)  :", level_order(root))

▶ Output

Preorder   (root, left, right): [4, 2, 1, 3, 6, 5, 7]
Inorder    (left, root, right): [1, 2, 3, 4, 5, 6, 7]
Postorder  (left, right, root): [1, 3, 2, 5, 7, 6, 4]
Level order (top to bottom)  : [4, 2, 6, 1, 3, 5, 7]

What happened here: The three recursive traversals differ only in where the current node’s value lands relative to its two recursive calls, and that one placement changes everything. Notice the inorder result is 1 2 3 4 5 6 7, perfectly sorted, which is not a coincidence: this tree was built so that smaller values sit on the left. That sorted-output property is the whole reason binary search trees exist, and it is the topic of the next section.

Level order is the odd one out because it is not recursive at all. It leans on a queue, pulling one node off the front and pushing its children onto the back, so the tree comes out row by row (4, then 2 6, then 1 3 5 7). That queue-driven, go-wide pattern is exactly BFS, which you will meet again on graphs in a moment.

Binary Search Trees and Why Balance Matters

A binary search tree (BST) keeps one promise: for every node, everything on its left is smaller and everything on its right is bigger. That promise turns search into a game of high-low. Looking for a value, you compare once and throw away half the remaining tree, then compare again and throw away half of what is left. When the tree is balanced, that is O(log n), the same halving trick as binary search. But there is a catch that trips up a lot of people, and it is worth measuring rather than just asserting.

Say a user named Anvay inserts his data already sorted, smallest first. Each new value is bigger than everything so far, so it always goes right, and the tree stops branching. It degenerates into what is basically a linked list: a single long spine. Now the halving trick is gone and search is O(n). Here is the same set of keys inserted two ways, one shuffled and one pre-sorted, with the height and the search cost measured for both.

📄 bst.py: the same keys, balanced versus degenerate

import random, sys

class BSTNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def insert(root, key):
    if root is None:
        return BSTNode(key)
    if key < root.key:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)
    return root

def search(root, key):
    steps, node = 0, root
    while node is not None:
        steps += 1
        if key == node.key:
            return steps
        node = node.left if key < node.key else node.right
    return steps

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

def build(keys):
    root = None
    for k in keys:
        root = insert(root, k)
    return root

sys.setrecursionlimit(20000)
n = 4095
random.seed(7)
balanced_keys = list(range(n)); random.shuffle(balanced_keys)  # random -> roughly balanced
sorted_keys = list(range(n))                                   # sorted -> degenerate spine

balanced = build(balanced_keys)
degenerate = build(sorted_keys)

target = n - 1  # worst case for the degenerate tree
print(f"Inserted {n} keys into two BSTs.")
print(f"{'tree':<12} | {'height':>7} | {'search steps for key ' + str(target):>26}")
print("-" * 52)
print(f"{'balanced':<12} | {height(balanced):>7} | {search(balanced, target):>26}")
print(f"{'degenerate':<12} | {height(degenerate):>7} | {search(degenerate, target):>26}")

▶ Output

Inserted 4095 keys into two BSTs.
tree         |  height |  search steps for key 4094
----------------------------------------------------
balanced     |      26 |                         10
degenerate   |    4095 |                       4095

What happened here: Same 4,095 keys, same BST code, wildly different results. The shuffled insert produced a tree only 26 levels tall, and finding a value took 10 comparisons. The pre-sorted insert produced a tree 4,095 levels tall, one node per level, and the same search took 4,095 comparisons. That is not a small difference, it is the gap between O(log n) and O(n) shown in real numbers. This is precisely why production code does not use a plain BST for large datasets.

It uses self-balancing variants that rotate nodes on insert to keep the height near log n, such as red-black trees and AVL trees. At the time of writing, Python’s own dict and set use hash tables instead (O(1) average lookup), and the standard-library bisect module gives you sorted-list search without hand-rolling a tree. Reach for those first; write your own BST to learn, not to ship.

Graphs, BFS, and DFS

The most common way to store a graph in Python is an adjacency dict: each key is a node, and its value is the list of neighbors it connects to. No special library, just a dictionary of lists. Once you have that, the two workhorse algorithms are BFS and DFS, and the difference between them is one data structure. BFS uses a queue and explores in expanding waves, level by level. DFS uses a stack (or plain recursion, which is a stack under the hood) and plunges down one path as far as it can before backing up. Same graph, same starting point, completely different order of visits.

Tip: click the diagram to open it full screen, then use the zoom and pan controls for a closer look.

The diagram shows both walks over the same little friend network starting from Aditi. BFS fans out: it visits everyone one hop away, then everyone two hops away, and so on. DFS commits to a single chain of friends and follows it to the end before it ever looks at Aditi’s second friend. Let’s build that network as an adjacency dict and run both, plus a shortest-path search that leans on the BFS wavefront.

📄 graph.py: BFS, DFS, and shortest path on a friend network

from collections import deque

# A tiny "who knows whom" network, stored as an adjacency dict.
social = {
    "Aditi":  ["Anvi", "Anvay"],
    "Anvi":   ["Aditi", "Aviraj"],
    "Anvay":  ["Aditi", "Meera"],
    "Aviraj": ["Anvi", "Rohan"],
    "Meera":  ["Anvay", "Rohan"],
    "Rohan":  ["Aviraj", "Meera", "Kabir"],
    "Kabir":  ["Rohan"],
}

def bfs(graph, start):
    visited, seen = [start], {start}
    queue = deque([start])
    while queue:
        person = queue.popleft()          # queue -> go wide
        for friend in graph[person]:
            if friend not in seen:
                seen.add(friend)
                visited.append(friend)
                queue.append(friend)
    return visited

def dfs(graph, start, seen=None, order=None):
    if seen is None:
        seen, order = set(), []
    seen.add(start)
    order.append(start)
    for friend in graph[start]:           # recursion -> go deep
        if friend not in seen:
            dfs(graph, friend, seen, order)
    return order

def shortest_path(graph, start, goal):
    queue = deque([[start]])              # a queue of PATHS, not just nodes
    seen = {start}
    while queue:
        path = queue.popleft()
        node = path[-1]
        if node == goal:
            return path                   # first time we reach it = shortest
        for friend in graph[node]:
            if friend not in seen:
                seen.add(friend)
                queue.append(path + [friend])
    return None

print("BFS from Aditi:", " -> ".join(bfs(social, "Aditi")))
print("DFS from Aditi:", " -> ".join(dfs(social, "Aditi")))
path = shortest_path(social, "Aditi", "Kabir")
print("Shortest path Aditi to Kabir:", " -> ".join(path))
print("Degrees of separation:", len(path) - 1)

▶ Output

BFS from Aditi: Aditi -> Anvi -> Anvay -> Aviraj -> Meera -> Rohan -> Kabir
DFS from Aditi: Aditi -> Anvi -> Aviraj -> Rohan -> Meera -> Anvay -> Kabir
Shortest path Aditi to Kabir: Aditi -> Anvi -> Aviraj -> Rohan -> Kabir
Degrees of separation: 4

What happened here: Look at the first two lines side by side. BFS reaches both of Aditi’s direct friends (Anvi, Anvay) before going any deeper, then their friends, spreading outward in rings. DFS grabs the first friend Anvi and dives: Anvi to Aviraj to Rohan, all the way to a dead end, and only then unwinds to pick up Meera and Anvay. The seen set in both functions is not optional decoration.

It is what stops the search from looping forever, because this graph has cycles (Aditi to Anvi to Aditi), and without a visited set you would bounce between them until Python’s stack gave out. The third line is the payoff: because BFS reaches nodes in order of distance, the very first time it touches the goal is guaranteed to be along a shortest path. That is why shortest_path queues whole paths and returns the moment it hits Kabir, giving four degrees of separation. DFS cannot make that promise, since it might reach the goal down a long detour first.

Where Trees and Graphs Show Up in Real Systems

This is not academic. Every day you use software that is running these exact walks. Your operating system’s file system is a tree, and a recursive folder-size tool is a postorder traversal totalling children before the parent. A package manager like pip or npm does dependency resolution by treating your requirements as a graph and running a topological sort, the same cycle-aware ordering used in the course-schedule drill below; if it finds a cycle, it reports a conflict instead of looping forever. Build tools, spreadsheet formula recalculation, and Git’s own commit history (a directed acyclic graph) all lean on the same ideas.

The idea reaches all the way into modern AI. A knowledge graph stores facts as nodes and relationships as edges (Aditi works at Acme, Acme is based in Pune), and retrieval systems walk that graph to gather context for a language model. That approach, GraphRAG, is exactly BFS and DFS over a knowledge graph instead of a friend network, and we build one later in this series in the post on GraphRAG and knowledge graphs. The dots and lines never change; only what the dots mean does.

Common Mistakes

❌ Mistake: Forgetting the visited set on a cyclic graph

# Bad: no 'seen' set. On a graph with a cycle this recurses forever.
def dfs_broken(graph, node):
    print(node)
    for friend in graph[node]:
        dfs_broken(graph, friend)   # Aditi -> Anvi -> Aditi -> Anvi -> ... crash

# Good: track what you have already visited.
def dfs_ok(graph, node, seen):
    if node in seen:
        return
    seen.add(node)
    print(node)
    for friend in graph[node]:
        dfs_ok(graph, friend, seen)

Why: A tree has no cycles, so tree recursion naturally ends at the leaves. A graph can loop, and the moment two nodes point at each other your search ping-pongs between them until you hit RecursionError or fill memory. The visited set is what turns “explore forever” into “explore each node once.” Add it every single time you touch a general graph.

❌ Mistake: Using a list as a queue for BFS

# Bad: list.pop(0) removes from the front, which is O(n) each call -> O(n^2) BFS
queue = [start]
node = queue.pop(0)      # shifts every remaining element down by one

# Good: collections.deque pops from the front in O(1)
from collections import deque
queue = deque([start])
node = queue.popleft()   # constant time, no matter how long the queue is

Why: A Python list is fast at the end but slow at the front, because pop(0) has to slide every other element over by one slot. Do that once per node in a BFS and your linear algorithm quietly becomes quadratic. A deque is built for exactly this: adding and removing at both ends is O(1). It is the right queue for BFS every time.

Best Practices

• Pick BFS for shortest paths, DFS for “does a path exist.” BFS visits nodes in distance order, so it finds the fewest-edges route. DFS goes deep with less memory and is natural for reachability, cycle detection, and topological sort.
• Always carry a visited set on graphs. Trees can skip it; general graphs cannot. It is the single line that separates a correct search from an infinite loop.
• Use collections.deque for BFS queues. A plain list makes front removal O(n) and turns linear BFS quadratic on big graphs.
• Do not ship a hand-rolled BST for large data. An unbalanced BST degrades to O(n). Reach for dict, set, or bisect, or a real balanced-tree library when you need ordered structure.
• Watch recursion depth on deep trees. Python’s default limit is around a thousand frames. For very deep structures, prefer an explicit stack with a while loop over deep recursion.

Wrapping Up

Trees and graphs come down to a small, durable set of ideas. A tree is a graph with no cycles and one parent per node, which buys you clean hierarchies and, in a search tree, sorted-order traversal. A graph drops those rules to model anything with connections. On top of both sit two searches: BFS goes wide with a queue and hands you shortest paths for free, while DFS goes deep with a stack and powers reachability, cycle detection, and ordering.

You saw all of it run, including the honest measurement that a pre-sorted BST balloons from 10 search steps to 4,095, which is why real systems use balanced trees and hash tables. None of this is tied to a framework or a version; the same code works in Python 3.14.6 today and will keep working long after the current AI tools are museum pieces.

Next in this chapter we turn these structures loose on classic interview problems and dynamic programming. the complete curriculum lives on the Python + AI/ML tutorial series home.

Frequently Asked Questions

Try It Yourself: Four Drills

These four problems are the classic interview uses of trees and graphs. Two are solved and run below; the other two are a challenge, and every one of them is just a traversal in disguise. Once you can spot that disguise, the coding interview patterns guide shows how the same handful of tricks covers whole families of problems. Tree height is the deepest path from root to leaf (the recursive height function you already saw in the BST code). Validate a BST checks that an inorder traversal comes out strictly increasing.

Count islands floods each patch of connected land in a grid. Course schedule asks whether a set of prerequisites can be finished, which is true only if the prerequisite graph has no cycle.

📄 drills.py: count islands and detect a prerequisite cycle

from collections import deque

# Drill 3: count islands of land ('1') connected up/down/left/right.
def count_islands(grid):
    rows, cols = len(grid), len(grid[0])
    seen, count = set(), 0

    def flood(r, c):
        stack = [(r, c)]
        while stack:
            y, x = stack.pop()
            if (y, x) in seen:
                continue
            if not (0 <= y < rows and 0 <= x < cols) or grid[y][x] != "1":
                continue
            seen.add((y, x))
            stack.extend([(y+1, x), (y-1, x), (y, x+1), (y, x-1)])

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1" and (r, c) not in seen:
                count += 1
                flood(r, c)
    return count

# Drill 4: can all courses be finished? True unless prerequisites form a cycle.
def can_finish(num_courses, prereqs):
    graph = {i: [] for i in range(num_courses)}
    indegree = [0] * num_courses
    for course, needs in prereqs:
        graph[needs].append(course)
        indegree[course] += 1
    queue = deque(c for c in range(num_courses) if indegree[c] == 0)
    done = 0
    while queue:                       # this is a BFS topological sort
        c = queue.popleft()
        done += 1
        for nxt in graph[c]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)
    return done == num_courses         # False means a cycle blocked us

grid = [list("11000"), list("11000"), list("00100"), list("00011")]
print("Islands in the grid:", count_islands(grid))
print("Can finish (no cycle):", can_finish(4, [(1, 0), (2, 1), (3, 2)]))
print("Can finish (has cycle):", can_finish(3, [(0, 1), (1, 2), (2, 0)]))

▶ Output

Islands in the grid: 3
Can finish (no cycle): True
Can finish (has cycle): False

What happened here: Count islands treats the grid as a graph where each land cell connects to its four neighbors, and each call to flood is a DFS that swallows one whole island, so the number of times you start a fresh flood is the number of islands: three here. Course schedule builds a prerequisite graph and repeatedly removes any course with no unmet prerequisites (indegree zero). If it manages to remove all of them, there is no cycle and you can finish; the moment a cycle exists, those courses never reach indegree zero and the count falls short, so it returns False.

Both problems sound different and are the same two traversals you have used all along. For the two challenge drills, try writing height(root) and an inorder-based is_valid_bst(root) yourself using the tree code from earlier.

Interview Questions on Trees and Graphs

Try each one aloud first. The phrasing you produce under mild pressure is what interviews measure.

Q: What is the difference between BFS and DFS, and which one finds the shortest path?

BFS uses a queue and explores nodes in expanding waves, one distance level at a time, while DFS uses a stack or recursion and follows one path to its end before backtracking. BFS finds the shortest path measured in number of edges, because the first time it reaches a node is guaranteed to be along a minimal-length route. DFS gives no such guarantee, since it may reach the target down a long branch first.

Q: How would you detect a cycle in a directed graph?

One clean way is a topological sort using indegrees (Kahn’s algorithm): repeatedly remove nodes with no incoming edges, and if you cannot remove every node, the ones left form a cycle. That is exactly the course-schedule drill. The alternative is DFS while tracking the current recursion path; if you reach a node that is already on the path you are exploring, you have found a back edge and therefore a cycle.

Q: Why can a binary search tree degrade to O(n), and how do real systems prevent it?

A BST stays O(log n) only while it is balanced. Insert keys in sorted order and every node goes to the same side, producing a single chain of height n, so search walks the whole thing. Real systems use self-balancing trees such as red-black or AVL trees that rotate nodes on insert to keep height near log n, or they sidestep trees entirely with hash-based structures like Python’s dict and set for O(1) average lookups.

Q: An inorder traversal of a binary search tree produces what, and how does that help validate one?

An inorder traversal of a valid BST produces the values in sorted, strictly increasing order. That gives a clean validation check: run an inorder traversal and confirm each value is greater than the previous one. If any value is less than or equal to its predecessor, the BST property is violated somewhere and the tree is invalid.

Q: Why is a deque preferred over a list for the BFS queue?

BFS removes nodes from the front of the queue. On a Python list, pop(0) is O(n) because every remaining element shifts down one slot, so a BFS over n nodes becomes O(n squared). A collections.deque removes from the front in O(1), keeping the BFS linear. It is the correct queue for any breadth-first search.

Q: When would you choose DFS over BFS in terms of memory?

DFS memory scales with the depth of the graph, since it only needs to hold the current path plus the visited set. BFS memory scales with the width, because the queue can hold an entire level at once, which on a wide graph is huge. For a very wide but shallow graph, DFS is far lighter; for shortest-path guarantees you accept BFS’s higher memory cost.

Go deeper: the official Python documentation covers every edge case of this topic.

Related Posts

Previous: Stacks and Queues in Python, Explained With deque

Next: Coding Interview Patterns in Python: Two Pointers, Sliding Window, DP

Series Home: Python + AI/ML Tutorial Series