In technical interviews, candidates rarely fail because of Python syntax—they get stuck when choosing the right non-linear or state-tracking data structure. While arrays (list) and hash maps (dict) get you through the initial phone screen, mid-level and senior interview rounds revolve around three core data structures:

  1. Stacks, Monotonic Stacks & Heaps: Matching nested structures, finding the "next greater/smaller element" in O(n) time, and managing priority queues.
  2. Trees (Binary Trees & BST): Modeling hierarchical data, breaking problems into recursive subproblems, and performing O(log n) search and ordered traversal.
  3. Graphs: Solving connected networks—from city maps and course prerequisites to microservice dependencies—using BFS, DFS, topological sort, and shortest-path algorithms.

In this guide, we break down Stacks, Trees, and Graphs with idiomatic Python templates and link directly to interactive PyMülakat problem pages where you can run and verify your code in the browser.


Quick Decision Table: Which Cue Points to Which Data Structure?

Problem Cue Data Structure / Pattern Time Complexity Practice Problem
Nested brackets, tags, undo history Stack (LIFO) O(n) K14: Valid Parentheses
"Next greater/smaller element", histogram, rainwater Monotonic Stack O(n) O27: Daily Temperatures
"Top K largest/smallest", merging K sorted lists Priority Queue (heapq) O(n log k) Z26: Merge K Sorted Lists
Hierarchy, depth, root-to-leaf path, subtree Binary Tree (DFS) O(n) K19: Maximum Depth
Ordered tree lookup, range query, Kth smallest Binary Search Tree (BST) O(h) O34: Kth Smallest in BST
Level-by-level traversal, right/left view Tree BFS (deque) O(n) O36: Binary Tree Right View
Unweighted shortest path, minimum steps, multi-source spread Graph BFS O(V + E) O42: Rotting Oranges
Number of islands, connected components, flood fill Graph DFS / BFS O(V + E) O43: Number of Islands
Prerequisites, task ordering, cycle detection Topological Sort O(V + E) O07: Task Order
Shortest path with positive edge weights Dijkstra (heapq) O((V + E) log V) Z35: Network Delay Time

1. Stacks, Monotonic Stacks, and Heaps

1.1 Classic Stack (LIFO — Last-In, First-Out)

Python's built-in list supports append() and pop() from the end in amortized O(1) time, making it a natural stack. Avoid list.pop(0) (which shifts every element in O(n)); reach for collections.deque whenever you need O(1) operations at both ends.

def is_valid_parentheses(s: str) -> bool:
    pairs = {")": "(", "]": "[", "}": "{"}
    stack: list[str] = []

    for ch in s:
        if ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
        else:
            stack.append(ch)

    return len(stack) == 0

print(is_valid_parentheses("({[]})"))  # True
print(is_valid_parentheses("([)]"))    # False

1.2 Monotonic Stack: Turning O(n²) Lookups into O(n)

When asked to find the next greater element for every item in an array, a monotonic decreasing stack stores indices whose answer hasn't been seen yet. As soon as a larger number arrives, it resolves all smaller pending indices in one pass. Because each index is pushed and popped at most once, total runtime is O(n).

def daily_temperatures(temps: list[int]) -> list[int]:
    n = len(temps)
    ans = [0] * n
    stack: list[int] = []  # indices waiting for a warmer day

    for today, temp in enumerate(temps):
        while stack and temps[stack[-1]] < temp:
            prev_day = stack.pop()
            ans[prev_day] = today - prev_day
        stack.append(today)

    return ans

print(daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]))
# [1, 1, 4, 2, 1, 1, 0, 0]

🎯 Practice Problems for Stacks & Heaps

👉 Explore the full module: Module 3: Stack, Queue & Linked List


2. Trees (Binary Trees & Binary Search Trees)

2.1 DFS vs. Level-Order BFS

from collections import deque

class TreeNode:
    def __init__(self, val: int = 0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def max_depth_dfs(root: TreeNode | None) -> int:
    if not root:
        return 0
    return 1 + max(max_depth_dfs(root.left), max_depth_dfs(root.right))

def right_side_view_bfs(root: TreeNode | None) -> list[int]:
    if not root:
        return []
    view: list[int] = []
    queue = deque([root])

    while queue:
        level_size = len(queue)
        for i in range(level_size):
            node = queue.popleft()
            if i == level_size - 1:
                view.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return view

2.2 Validating a Binary Search Tree (BST)

def is_valid_bst(root: TreeNode | None,
                 low: float = float("-inf"),
                 high: float = float("inf")) -> bool:
    if not root:
        return True
    if not (low < root.val < high):
        return False
    return (is_valid_bst(root.left, low, root.val) and
            is_valid_bst(root.right, root.val, high))

🎯 Practice Problems for Trees & BST

👉 Explore the full module: Module 4: Trees & BST


3. Graphs: BFS, DFS, Topological Sort, and Dijkstra

3.1 Topological Sort (Kahn's Algorithm)

from collections import defaultdict, deque

def find_task_order(num_tasks: int, prerequisites: list[tuple[int, int]]) -> list[int]:
    graph: dict[int, list[int]] = defaultdict(list)
    in_degree = [0] * num_tasks

    for task, prereq in prerequisites:
        graph[prereq].append(task)
        in_degree[task] += 1

    queue = deque(i for i, d in enumerate(in_degree) if d == 0)
    order: list[int] = []

    while queue:
        curr = queue.popleft()
        order.append(curr)
        for nxt in graph[curr]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                queue.append(nxt)

    return order if len(order) == num_tasks else []

3.2 Weighted Shortest Path: Dijkstra's Algorithm

from collections import defaultdict
import heapq

def dijkstra_shortest_times(n: int, edges: list[tuple[int, int, int]], source: int) -> dict[int, int]:
    graph: dict[int, list[tuple[int, int]]] = defaultdict(list)
    for u, v, w in edges:
        graph[u].append((v, w))

    dist: dict[int, int] = {}
    heap: list[tuple[int, int]] = [(0, source)]

    while heap:
        cost, u = heapq.heappop(heap)
        if u in dist:
            continue
        dist[u] = cost
        for v, w in graph[u]:
            if v not in dist:
                heapq.heappush(heap, (cost + w, v))

    return dist

🎯 Practice Problems for Graphs

👉 Explore the full module: Module 5: Graphs

Interactive Practice Station

Ready to Test Theory in a Real Exam Environment?

10 specialization modules and 200 original Python interview problems await you on PyMülakat. Write and run your code in the browser and test yourself against hidden boundary cases.

Solve First Problem (K01) →Explore Modules