Intermediate Data Structures: Trees and Graphs

Welcome to connected data

Now that you've covered Introduction to Data Structures, Algorithm Basics and Complexity Analysis, and Recursive Algorithms and Backtracking, you're ready for structures where data points are connected instead of simply lined up.

Today we focus on two big interview families:

• Trees: hierarchical relationships, like folders, comments, family trees, decision paths
• Graphs: general relationships, like maps, friendships, dependencies, networks

The key shift: instead of asking “what is the next index?”, we ask “what neighbors can I reach from here?”

By the end, you should be able to recognize tree/graph problems, choose a representation, and traverse connected data confidently in Python.

A tree is a one-way hierarchy

A tree is a set of connected nodes with one starting point called the root.

Common vocabulary:

• Node: one item in the tree
• Root: top node
• Parent / child: direct relationship between levels
• Leaf: node with no children
• Subtree: any node plus everything below it
• Height: longest path from a node down to a leaf

Example:

        A
      /   \
     B     C
    / \     \
   D   E     F

Here, A is the root. D, E, and F are leaves. The subtree at B contains B, D, and E.

Because trees branch, recursion from the previous lesson is a natural fit: solve the current node, then solve its children.

Visiting a tree with DFS

A traversal is a rule for visiting every node.

For binary trees, three classic depth-first orders are:

• Preorder: node → left → right
• Inorder: left → node → right
• Postorder: left → right → node

These names are about when we process the current node.

This builds directly on the recursive function anatomy you practiced earlier: each traversal has a base case for None, then recursive calls for child nodes.

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

#        A
#      /   \
#     B     C
#    / \     \
#   D   E     F
root = Node("A",
    Node("B", Node("D"), Node("E")),
    Node("C", None, Node("F"))
)

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]

print("preorder:", preorder(root))
print("inorder:", inorder(root))
print("postorder:", postorder(root))
```

For the tree below, which traversal order is preorder?

    1
   / \
  2   3

Remember: preorder processes the current node before its children.

A tree that keeps order

A Binary Search Tree, or BST, is a binary tree with an ordering rule:

• values in the left subtree are smaller
• values in the right subtree are larger

Example:

        8
      /   \
     3     10
    / \      \
   1   6      14

This rule lets us search like a decision path:

• if target is smaller, go left
• if target is larger, go right
• if equal, found it

Complexity depends on height:

• Balanced-ish tree: O(log n) search
• Skewed tree: O(n) search

That complexity connection should feel familiar from Algorithm Basics and Complexity Analysis: the same operation can have different cost depending on the data shape.

Graphs are general connections

A graph has:

• vertices: the items, also called nodes
• edges: the connections between items

Graphs can be:

• Undirected: friendship-style, A -- B
• Directed: one-way, A -> B
• Weighted: edges have costs, like distances or prices

For now, we will focus on unweighted traversal. Shortest paths and deeper connectivity patterns come later.

Common Python representation

Most beginner-friendly graph problems use an adjacency list:

A: B, C
B: A, D
C: A
D: B

In Python, that often becomes a dictionary where each key maps to a list of neighbors.

True or false?

With a basic adjacency list using Python lists, checking whether there is an edge from u to v is always O(1).

Two ways to explore a graph

For unweighted graph traversal, two core tools are:

• DFS: go deep before backing up
• BFS: explore layer by layer

Mental model:

DFS: follow one path as far as possible
BFS: visit all distance-1 nodes, then distance-2 nodes, ...

Both need a visited set so we do not loop forever in cycles.

Use DFS when you naturally want to explore paths or components. Use BFS when the idea of “layers” matters. We are not doing shortest-path algorithms yet, but BFS’s layer behavior will become important later.

```python
from collections import deque

graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"]
}

def dfs(start):
    visited = set()
    order = []

    def visit(node):
        if node in visited:
            return
        visited.add(node)
        order.append(node)
        for neighbor in graph[node]:
            visit(neighbor)

    visit(start)
    return order

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

    while queue:
        node = queue.popleft()
        order.append(node)

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

    return order

print("DFS from A:", dfs("A"))
print("BFS from A:", bfs("A"))
```

BFS explores a graph in layers, so its frontier is usually stored in a ____.

What to practice today

Trees and graphs are where many medium problems start to feel different from array/string problems. The data is no longer just a sequence; it is a set of relationships.

Your core checklist

When you see a connected-data problem, ask:

1. Is it a tree or a graph?
2. Do I need recursion, a stack, or a queue?
3. What counts as visited?
4. What is the cost in nodes and edges?

Typical traversal complexity:

• Tree traversal: O(n) time, because each node is visited once
• Graph traversal: O(V + E) time, because we visit vertices and inspect edges

2-day revisit habit

Since this crash course includes revisiting problems every 2 days, put these into your rotation:

• traverse a binary tree in preorder/inorder/postorder
• search in a BST
• BFS from a starting graph node
• DFS with a visited set

Next, you will shift into Dynamic Programming Essentials, where recursion returns with a new twist: remembering overlapping subproblem results.