Intermediate Examples

"""Example 29: Reverse a Singly Linked List Iteratively."""
 
from __future__ import (
    annotations,
)  # => enables forward references to the class defined below
 
 
class Node:  # => the standard singly-linked node shape (co-07)
    def __init__(self, val: int, next: Node | None = None) -> None:  # => constructor
        self.val = val  # => the value stored at this node
        self.next = next  # => pointer to the next node, or None at the tail
 
 
# Flips every .next pointer to point backward -- one O(n) pass, O(1) extra space (co-07).
def reverse(head: Node | None) -> Node | None:  # => rewires the chain in place
    previous: Node | None = None  # => will become the new head once the loop finishes
    current = head  # => the node currently being rewired
    while current is not None:  # => walks forward through the ORIGINAL chain
        next_node = current.next  # => save the forward link BEFORE overwriting it
        current.next = previous  # => rewire: point this node back at the previous one
        previous = current  # => advance "previous" to this now-rewired node
        current = next_node  # => advance "current" using the saved forward link
    return previous  # => previous ends up at the old TAIL -- the new head
 
 
# Collects node values in link order for easy comparison.
def to_list(head: Node | None) -> list[int]:  # => a plain traversal helper
    values: list[int] = []  # => accumulates values as the chain is walked
    node = head  # => starts traversal at head
    while node is not None:  # => stops once the tail's next is None
        values.append(node.val)  # => records this node's value
        node = node.next  # => advances one link forward
    return values  # => the values in link order
 
 
original = Node(1, Node(2, Node(3, Node(4))))  # => 1 -> 2 -> 3 -> 4
reversed_head = reverse(
    original
)  # => rewires in place -- returns the new head (old node 4)
print(to_list(reversed_head))  # => Output: [4, 3, 2, 1]
 
assert to_list(reversed_head) == [4, 3, 2, 1]  # => confirms the chain is fully reversed
print("ex-29 OK")  # => Output: ex-29 OK

[4, 3, 2, 1]
ex-29 OK

"""Example 30: Find the Middle Node with Slow/Fast Pointers."""
 
from __future__ import (
    annotations,
)  # => enables forward references to the class defined below
 
 
class Node:  # => the standard singly-linked node shape (co-07)
    def __init__(self, val: int, next: Node | None = None) -> None:  # => constructor
        self.val = val  # => the value stored at this node
        self.next = next  # => pointer to the next node, or None at the tail
 
 
# Advances slow by 1 and fast by 2 each step -- when fast hits the end, slow is at
# the middle -- one traversal, no length pre-count needed (co-07, co-20).
def middle_value(head: Node | None) -> int:  # => a two-pointer traversal
    slow = head  # => the "tortoise" -- moves one node per step
    fast = head  # => the "hare" -- moves two nodes per step
    while fast is not None and fast.next is not None:  # => stop when fast runs out
        assert (
            slow is not None
        )  # => invariant: slow never runs past fast, so it's always live here
        slow = slow.next  # => tortoise: +1 node
        fast = fast.next.next  # => hare: +2 nodes -- reaches the end twice as fast
    assert slow is not None  # => the list is non-empty in this example
    return slow.val  # => when fast finishes, slow sits exactly at the middle
 
 
odd_list = Node(1, Node(2, Node(3, Node(4, Node(5)))))  # => 5 nodes: middle is 3
middle = middle_value(odd_list)  # => slow lands on the node holding 3
print(middle)  # => Output: 3
 
assert middle == 3  # => confirms the two-pointer walk found the true middle
print("ex-30 OK")  # => Output: ex-30 OK

3
ex-30 OK

"""Example 31: Iterative Binary Search."""
 
 
# Halves the candidate range each step -- requires a SORTED input, O(log n) (co-14).
def binary_search(
    items: list[int], target: int
) -> int:  # => a plain iterative function
    low, high = 0, len(items) - 1  # => the inclusive range still being searched
    while low <= high:  # => keeps narrowing until the range is empty
        mid = (low + high) // 2  # => the midpoint of the current range
        if items[mid] == target:  # => a direct hit at the midpoint
            return mid  # => found -- return immediately, no more halving needed
        if items[mid] < target:  # => the midpoint is too small
            low = mid + 1  # => target must be in the RIGHT half -- discard the left
        else:  # => the midpoint is too large
            high = mid - 1  # => target must be in the LEFT half -- discard the right
    return -1  # => range emptied out with no match
 
 
sorted_values = [1, 3, 5, 7, 9, 11, 13]  # => MUST be sorted for binary search to work
index = binary_search(sorted_values, 9)  # => 9 sits at index 4
print(index)  # => Output: 4
 
assert index == 4  # => confirms the returned index matches sorted_values[4]
assert sorted_values[index] == 9  # => confirms indexing back recovers the target
print("ex-31 OK")  # => Output: ex-31 OK

4
ex-31 OK

"""Example 32: Binary Search -- Value Not Found."""
 
 
# Same halving search as Example 31; -1 signals "absent" (co-14).
def binary_search(
    items: list[int], target: int
) -> int:  # => a plain iterative function
    low, high = 0, len(items) - 1  # => the inclusive range still being searched
    while low <= high:  # => O(log n): the range shrinks by half every iteration
        mid = (low + high) // 2  # => the midpoint of the current range
        if items[mid] == target:  # => not true anywhere in this fixture
            return mid  # => not reached in this example
        if items[mid] < target:  # => the midpoint is too small
            low = mid + 1  # => target must be in the RIGHT half -- discard the left
        else:  # => the midpoint is too large
            high = mid - 1  # => target must be in the LEFT half -- discard the right
    return -1  # => low crosses high with no match -- the range is now empty
 
 
sorted_values = [1, 3, 5, 7, 9, 11, 13]  # => the same sorted list as Example 31
index = binary_search(
    sorted_values, 6
)  # => 6 is not present -- it would sit between 5 and 7
print(index)  # => Output: -1
 
assert (
    index == -1
)  # => confirms a missing value returns the sentinel, not a wrong index
assert 6 not in sorted_values  # => confirms the target really is absent from the source
print("ex-32 OK")  # => Output: ex-32 OK

-1
ex-32 OK

"""Example 33: Binary Search -- Leftmost (First) Occurrence."""
 
 
# Keeps searching LEFT even after a match, to find the first duplicate (co-14).
def find_first(items: list[int], target: int) -> int:  # => a plain iterative function
    low, high = 0, len(items) - 1  # => the inclusive range still being searched
    result = -1  # => tracks the best (leftmost) match found so far
    while (
        low <= high
    ):  # => still O(log n) -- one extra comparison per step, not a rescan
        mid = (low + high) // 2  # => the midpoint of the current range
        if (
            items[mid] == target
        ):  # => a candidate match -- but maybe not the leftmost one
            result = mid  # => record this match...
            high = mid - 1  # => ...then keep searching the LEFT half for an earlier one
        elif items[mid] < target:  # => the midpoint is too small
            low = mid + 1  # => target must be further right
        else:  # => the midpoint is too large
            high = mid - 1  # => target must be further left
    return result  # => the smallest index where target was ever recorded
 
 
duplicates = [1, 2, 2, 2, 3, 4]  # => target 2 appears at indices 1, 2, and 3
first_index = find_first(duplicates, 2)  # => the leftmost occurrence is index 1
print(first_index)  # => Output: 1
 
assert first_index == 1  # => confirms the leftmost occurrence, not just any match
print("ex-33 OK")  # => Output: ex-33 OK

1
ex-33 OK

"""Example 34: Binary Search -- Rightmost (Last) Occurrence."""
 
 
# Mirror image of Example 33: keeps searching RIGHT after a match (co-14).
def find_last(items: list[int], target: int) -> int:  # => a plain iterative function
    low, high = 0, len(items) - 1  # => the inclusive range still being searched
    result = -1  # => tracks the best (rightmost) match found so far
    while low <= high:  # => O(log n) -- same shape as find_first, mirrored
        mid = (low + high) // 2  # => the midpoint of the current range
        if (
            items[mid] == target
        ):  # => a candidate match -- but maybe not the rightmost one
            result = mid  # => record this match...
            low = mid + 1  # => ...then keep searching the RIGHT half for a later one
        elif items[mid] < target:  # => the midpoint is too small
            low = mid + 1  # => target must be further right
        else:  # => the midpoint is too large
            high = mid - 1  # => target must be further left
    return result  # => the largest index where target was ever recorded
 
 
duplicates = [1, 2, 2, 2, 3, 4]  # => target 2 appears at indices 1, 2, and 3
last_index = find_last(duplicates, 2)  # => the rightmost occurrence is index 3
print(last_index)  # => Output: 3
 
assert (
    last_index == 3
)  # => confirms the rightmost occurrence, not the first match found
print("ex-34 OK")  # => Output: ex-34 OK

3
ex-34 OK

"""Example 35: bisect.bisect_left -- Sorted Insertion Point."""
 
# bisect_left finds WHERE a value would go to keep the list sorted, in O(log n),
# without actually inserting it -- the stdlib's binary search, ready-made (co-14).
import bisect
 
sorted_values: list[int] = [1, 3, 5, 7, 9]  # => must already be sorted
point_for_present = bisect.bisect_left(
    sorted_values, 5
)  # => 5 already exists at index 2
point_for_absent = bisect.bisect_left(sorted_values, 6)  # => 6 belongs between 5 and 7
print(point_for_present)  # => Output: 2
print(point_for_absent)  # => Output: 3
 
assert (
    point_for_present == 2
)  # => confirms bisect_left lands ON an existing equal value
assert point_for_absent == 3  # => confirms the insertion index for a missing value
print("ex-35 OK")  # => Output: ex-35 OK

2
3
ex-35 OK

"""Example 36: bisect.insort -- Insert While Staying Sorted."""
 
# insort finds the sorted position (O(log n) search) then inserts (O(n) shift) --
# cheaper than appending and re-sorting the whole list every time (co-14, co-03).
import bisect
 
sorted_values: list[int] = [1, 3, 5, 9]  # => already sorted ascending
bisect.insort(sorted_values, 7)  # => inserts 7 at the position that keeps order intact
print(sorted_values)  # => Output: [1, 3, 5, 7, 9]
 
assert sorted_values == [
    1,
    3,
    5,
    7,
    9,
]  # => confirms the list stayed sorted after insert
assert sorted_values == sorted(sorted_values)  # => cross-checks against sorted() itself
print("ex-36 OK")  # => Output: ex-36 OK

[1, 3, 5, 7, 9]
ex-36 OK

"""Example 37: Min-Heap with heapq.heappush and heappop."""
 
# heapq maintains list[0] as the smallest element at all times -- push and pop
# are both O(log n), the cost of re-balancing the binary heap (co-12).
import heapq
 
heap: list[int] = []  # => an ordinary list, treated as a heap by the heapq functions
for value in (5, 1, 8, 3):  # => pushes in arbitrary order, not sorted order
    heapq.heappush(
        heap, value
    )  # => O(log n): inserts, then bubbles up to restore heap order
 
popped_order: list[int] = []  # => collects pops to prove ascending order
while heap:  # => drains the heap completely
    popped_order.append(
        heapq.heappop(heap)
    )  # => O(log n): always removes the CURRENT min
print(popped_order)  # => Output: [1, 3, 5, 8]
 
assert popped_order == [
    1,
    3,
    5,
    8,
]  # => confirms heappop always returns ascending order
print("ex-37 OK")  # => Output: ex-37 OK

[1, 3, 5, 8]
ex-37 OK

"""Example 38: heapq.heapify -- Turn a List into a Heap In Place."""
 
# heapify rearranges an EXISTING list into heap order in O(n) -- faster than
# pushing every element one at a time, which would cost O(n log n) (co-12).
import heapq
 
values: list[int] = [9, 4, 7, 1, 3]  # => an unordered list, not yet heap-shaped
heapq.heapify(values)  # => O(n): rearranges values in place into a valid min-heap
print(values[0])  # => Output: 1 (the minimum -- always at index 0 after heapify)
 
assert values[0] == min([9, 4, 7, 1, 3])  # => confirms heap[0] equals the true minimum
assert heapq.heappop(values) == 1  # => confirms popping still yields the minimum first
print("ex-38 OK")  # => Output: ex-38 OK

1
ex-38 OK

"""Example 39: Top-K Largest with heapq.nlargest."""
 
# heapq.nlargest keeps only a size-k heap while scanning, O(n log k) --
# cheaper than sorted(values)[-k:], which pays O(n log n) for the WHOLE list (co-12).
import heapq
 
values: list[int] = [5, 1, 9, 3, 7, 2]  # => 6 values, only the top 3 are wanted
top_three = heapq.nlargest(3, values)  # => returns the 3 largest, in descending order
print(top_three)  # => Output: [9, 7, 5]
 
assert top_three == [9, 7, 5]  # => confirms the exact top-3 values in descending order
assert set(top_three) == {5, 7, 9}  # => cross-checks the SET of values, order aside
print("ex-39 OK")  # => Output: ex-39 OK

[9, 7, 5]
ex-39 OK

"""Example 40: Priority Queue with (priority, task) Tuples."""
 
# heapq compares TUPLES element-by-element, so a (priority, task) tuple sorts
# by priority first -- the standard way to build a priority queue (co-12).
import heapq
 
tasks: list[
    tuple[int, str]
] = []  # => each entry is (priority, task_name); lower = more urgent
heapq.heappush(tasks, (3, "cleanup"))  # => low urgency
heapq.heappush(
    tasks, (1, "fix outage")
)  # => highest urgency -- smallest priority number
heapq.heappush(tasks, (2, "deploy"))  # => medium urgency
 
order: list[str] = []  # => records the order tasks are served in
while tasks:  # => drains the heap, always taking the lowest-priority-number tuple first
    priority, task = heapq.heappop(
        tasks
    )  # => unpacks the popped (priority, task) tuple
    order.append(task)  # => records just the task name for the assertion below
print(order)  # => Output: ['fix outage', 'deploy', 'cleanup']
 
assert order == [
    "fix outage",
    "deploy",
    "cleanup",
]  # => confirms urgent-first pop order
print("ex-40 OK")  # => Output: ex-40 OK

['fix outage', 'deploy', 'cleanup']
ex-40 OK

"""Example 41: Max-Heap via Negation."""
 
# heapq only implements a MIN-heap. Negating every value on the way in flips the
# ordering: the smallest negative (== the largest original value) pops first (co-12).
import heapq  # => imports the stdlib binary-heap functions
 
max_heap: list[int] = []  # => stores NEGATED values internally
for value in (5, 1, 8, 3):  # => pushes each source value in turn
    heapq.heappush(
        max_heap, -value
    )  # => pushes -5, -1, -8, -3 -- min-heap on negatives
 
largest = -heapq.heappop(
    max_heap
)  # => pops the smallest negative (-8), then negates back
second_largest = -heapq.heappop(max_heap)  # => pops the next smallest negative (-5)
print(largest, second_largest)  # => Output: 8 5
 
assert largest == 8  # => confirms the true maximum popped first
assert second_largest == 5  # => confirms the second-largest popped next
print("ex-41 OK")  # => Output: ex-41 OK

8 5
ex-41 OK

"""Example 42: Merge Two Sorted Lists with heapq.merge."""
 
# heapq.merge streams both inputs through a small heap, producing sorted output
# without concatenating and re-sorting -- O(n) for two already-sorted inputs (co-12, co-15).
import heapq
 
left: list[int] = [1, 4, 7]  # => already sorted
right: list[int] = [2, 3, 8]  # => already sorted
merged = list(
    heapq.merge(left, right)
)  # => lazily interleaves both inputs in sorted order
print(merged)  # => Output: [1, 2, 3, 4, 7, 8]
 
assert merged == [1, 2, 3, 4, 7, 8]  # => confirms full interleaved sorted order
assert merged == sorted(
    left + right
)  # => cross-checks against a plain sort of the union
print("ex-42 OK")  # => Output: ex-42 OK

[1, 2, 3, 4, 7, 8]
ex-42 OK

"""Example 43: Insertion Sort."""
 
 
# Grows a sorted prefix one element at a time -- O(n^2) worst case (co-16).
def insertion_sort(items: list[int]) -> list[int]:  # => a plain sorting function
    values = items.copy()  # => works on a copy so the caller's list is untouched
    for i in range(1, len(values)):  # => values[:i] is already sorted at each step
        key = values[i]  # => the element being inserted into the sorted prefix
        j = i - 1  # => scans backward through the sorted prefix
        while j >= 0 and values[j] > key:  # => shifts larger elements one slot right
            values[j + 1] = values[j]  # => makes room for key
            j -= 1  # => continues scanning backward
        values[j + 1] = key  # => drops key into its now-correct position
    return values  # => the fully sorted list
 
 
unsorted = [5, 2, 4, 6, 1, 3]  # => a small unsorted list
result = insertion_sort(unsorted)  # => builds a sorted prefix left to right
print(result)  # => Output: [1, 2, 3, 4, 5, 6]
 
assert result == sorted(unsorted)  # => confirms the hand-rolled sort matches sorted()
print("ex-43 OK")  # => Output: ex-43 OK

[1, 2, 3, 4, 5, 6]
ex-43 OK

"""Example 44: Selection Sort."""
 
 
# Repeatedly finds the minimum of the unsorted tail and swaps it forward -- O(n^2) (co-16).
def selection_sort(items: list[int]) -> list[int]:  # => a plain sorting function
    values = items.copy()  # => works on a copy so the caller's list is untouched
    for i in range(len(values)):  # => values[:i] is the growing sorted prefix
        min_index = (
            i  # => assume the current position holds the smallest remaining value
        )
        for j in range(i + 1, len(values)):  # => O(n) linear scan for the true minimum
            if values[j] < values[min_index]:  # => found a smaller candidate
                min_index = j  # => track its index for the swap below
        values[i], values[min_index] = (
            values[min_index],
            values[i],
        )  # => one swap per outer pass
    return values  # => the fully sorted list
 
 
unsorted = [5, 2, 4, 6, 1, 3]  # => the same fixture as Example 43
result = selection_sort(unsorted)  # => finds+places the minimum, n times over
print(result)  # => Output: [1, 2, 3, 4, 5, 6]
 
assert result == sorted(unsorted)  # => confirms the hand-rolled sort matches sorted()
print("ex-44 OK")  # => Output: ex-44 OK

[1, 2, 3, 4, 5, 6]
ex-44 OK

"""Example 45: Bubble Sort."""
 
 
# Repeatedly swaps adjacent out-of-order pairs -- large values "bubble" to the end (co-16).
def bubble_sort(items: list[int]) -> list[int]:  # => a plain sorting function
    values = items.copy()  # => works on a copy so the caller's list is untouched
    n = len(values)  # => cached length, reused every outer pass
    for i in range(n):  # => after pass i, the LAST i elements are guaranteed sorted
        swapped = False  # => tracks whether this pass did any work at all
        for j in range(
            n - 1 - i
        ):  # => shrinks the unsorted range by one each outer pass
            if values[j] > values[j + 1]:  # => adjacent pair is out of order
                values[j], values[j + 1] = values[j + 1], values[j]  # => swap them
                swapped = True  # => records that this pass made progress
        if not swapped:  # => a pass with zero swaps means the list is already sorted
            break  # => early exit -- avoids wasted passes, still O(n^2) worst case
    return values  # => the fully sorted list
 
 
unsorted = [5, 2, 4, 6, 1, 3]  # => the same fixture as Examples 43-44
result = bubble_sort(unsorted)  # => large values bubble rightward each pass
print(result)  # => Output: [1, 2, 3, 4, 5, 6]
 
assert result == sorted(unsorted)  # => confirms the hand-rolled sort matches sorted()
print("ex-45 OK")  # => Output: ex-45 OK

[1, 2, 3, 4, 5, 6]
ex-45 OK

"""Example 46: Recursive Merge Sort."""
 
 
# Splits in half recursively, then merges sorted halves -- guaranteed O(n log n) (co-16, co-17).
def merge_sort(items: list[int]) -> list[int]:  # => the recursive driver
    if len(items) <= 1:  # => BASE CASE -- a list of 0 or 1 elements is already sorted
        return items  # => nothing to sort
    mid = len(items) // 2  # => splits the list into two roughly equal halves
    left = merge_sort(items[:mid])  # => RECURSIVE CASE: sort the left half
    right = merge_sort(items[mid:])  # => RECURSIVE CASE: sort the right half
    return _merge(left, right)  # => combine two SORTED halves into one sorted list
 
 
# Interleaves two sorted lists into one sorted list -- O(n) linear merge.
def _merge(left: list[int], right: list[int]) -> list[int]:  # => a merge helper
    merged: list[int] = []  # => the combined, sorted result
    i = j = 0  # => independent cursors into left and right
    while i < len(left) and j < len(
        right
    ):  # => picks the smaller front element each step
        if left[i] <= right[j]:  # => the left cursor's element is smaller-or-equal
            merged.append(left[i])  # => takes from the left side
            i += 1  # => advances the left cursor
        else:  # => the right cursor's element is smaller
            merged.append(right[j])  # => takes from the right side
            j += 1  # => advances the right cursor
    merged.extend(left[i:])  # => appends whichever side has leftovers -- already sorted
    merged.extend(right[j:])  # => appends any remaining right-side leftovers too
    return merged  # => the fully merged, sorted list
 
 
unsorted = [5, 2, 4, 6, 1, 3]  # => the same fixture as prior sorting examples
result = merge_sort(unsorted)  # => splits down to singletons, then merges back up
print(result)  # => Output: [1, 2, 3, 4, 5, 6]
 
assert result == sorted(unsorted)  # => confirms the hand-rolled sort matches sorted()
print("ex-46 OK")  # => Output: ex-46 OK

[1, 2, 3, 4, 5, 6]
ex-46 OK

"""Example 47: Recursive Quicksort."""
 
 
# Partitions around a pivot, recurses on both sides -- O(n log n) average, but O(n^2)
# worst case with a poor pivot choice, e.g. an already-sorted input (co-16, co-17).
def quicksort(items: list[int]) -> list[int]:  # => the recursive driver
    if len(items) <= 1:  # => BASE CASE -- 0 or 1 elements are trivially sorted
        return items  # => nothing to sort
    pivot = items[len(items) // 2]  # => picks a middle element as the pivot
    less = [x for x in items if x < pivot]  # => everything strictly smaller than pivot
    equal = [
        x for x in items if x == pivot
    ]  # => every occurrence of the pivot value itself
    greater = [
        x for x in items if x > pivot
    ]  # => everything strictly larger than pivot
    return (
        quicksort(less) + equal + quicksort(greater)
    )  # => RECURSIVE CASE: sort each part
 
 
unsorted = [5, 2, 4, 6, 1, 3]  # => the same fixture as prior sorting examples
result = quicksort(
    unsorted
)  # => partitions around a pivot, then recurses on both sides
print(result)  # => Output: [1, 2, 3, 4, 5, 6]
 
assert result == sorted(unsorted)  # => confirms the hand-rolled sort matches sorted()
print("ex-47 OK")  # => Output: ex-47 OK

[1, 2, 3, 4, 5, 6]
ex-47 OK

"""Example 48: Build a Binary Tree."""
 
from __future__ import (
    annotations,
)  # => enables forward references to the class defined below
from collections import (
    deque,
)  # => imports the stdlib double-ended queue for the BFS below
 
 
class TreeNode:  # => a node with up to two children: left and right (co-10, co-22)
    def __init__(
        self, val: int, left: TreeNode | None = None, right: TreeNode | None = None
    ) -> None:  # => constructor: stores the value plus both optional children
        self.val = val  # => the value stored at this node
        self.left = left  # => reference to the left child, or None
        self.right = right  # => reference to the right child, or None
 
 
#        4
#       / \
#      2   6
#     / \
#    1   3
root = TreeNode(
    4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(6)
)  # => builds by hand
 
level_order: list[int] = []  # => collects values level by level, to eyeball the shape
queue: deque[TreeNode] = deque([root])  # => a queue seeded with just the root
while queue:  # => classic BFS: visit, then enqueue children, until the queue is empty
    node = queue.popleft()  # => dequeues the next node to visit, O(1)
    level_order.append(node.val)  # => records this node's value
    if node.left:  # => a left child exists
        queue.append(node.left)  # => enqueues it for a later visit
    if node.right:  # => a right child exists
        queue.append(node.right)  # => enqueues it for a later visit
print(level_order)  # => Output: [4, 2, 6, 1, 3]
 
assert level_order == [4, 2, 6, 1, 3]  # => confirms the tree's exact level-order shape
print("ex-48 OK")  # => Output: ex-48 OK

[4, 2, 6, 1, 3]
ex-48 OK

"""Example 49: Recursive Inorder Traversal."""
 
from __future__ import (
    annotations,
)  # => enables forward references to the class defined below
 
 
class TreeNode:  # => the same binary-tree node shape as Example 48 (co-10)
    def __init__(
        self, val: int, left: TreeNode | None = None, right: TreeNode | None = None
    ) -> None:  # => constructor: stores the value plus both optional children
        self.val = val  # => the value stored at this node
        self.left = left  # => reference to the left child, or None
        self.right = right  # => reference to the right child, or None
 
 
# Visits left, THEN self, THEN right -- depth-first, recursive (co-10, co-17).
def inorder(node: TreeNode | None) -> list[int]:  # => a plain recursive traversal
    if node is None:  # => BASE CASE -- an empty subtree contributes nothing
        return []  # => no values from this branch
    return inorder(node.left) + [node.val] + inorder(node.right)  # => left, self, right
 
 
#        4
#       / \
#      2   6
#     / \
#    1   3
root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(6))
values = inorder(root)  # => visits 1, 2, 3, 4, 6 -- left subtree, root, right subtree
print(values)  # => Output: [1, 2, 3, 4, 6]
 
assert values == [1, 2, 3, 4, 6]  # => confirms the exact left-root-right visit order
print("ex-49 OK")  # => Output: ex-49 OK

[1, 2, 3, 4, 6]
ex-49 OK

"""Example 50: Preorder and Postorder Traversals."""
 
from __future__ import (
    annotations,
)  # => enables forward references to the class defined below
 
 
class TreeNode:  # => the same binary-tree node shape as Example 48 (co-10)
    def __init__(
        self, val: int, left: TreeNode | None = None, right: TreeNode | None = None
    ) -> None:  # => constructor: stores the value plus both optional children
        self.val = val  # => the value stored at this node
        self.left = left  # => reference to the left child, or None
        self.right = right  # => reference to the right child, or None
 
 
# Visits self, THEN left, THEN right (co-10, co-17).
def preorder(node: TreeNode | None) -> list[int]:  # => a plain recursive traversal
    if node is None:  # => BASE CASE -- nothing to visit
        return []  # => no values from this branch
    return (
        [node.val] + preorder(node.left) + preorder(node.right)
    )  # => self, left, right
 
 
# Visits left, THEN right, THEN self -- self is visited LAST (co-10, co-17).
def postorder(node: TreeNode | None) -> list[int]:  # => a plain recursive traversal
    if node is None:  # => BASE CASE -- nothing to visit
        return []  # => no values from this branch
    return (
        postorder(node.left) + postorder(node.right) + [node.val]
    )  # => left, right, self
 
 
#        4
#       / \
#      2   6
#     / \
#    1   3
root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(6))
pre = preorder(root)  # => root first: 4, 2, 1, 3, 6
post = postorder(root)  # => root last: 1, 3, 2, 6, 4
print(pre)  # => Output: [4, 2, 1, 3, 6]
print(post)  # => Output: [1, 3, 2, 6, 4]
 
assert pre == [
    4,
    2,
    1,
    3,
    6,
]  # => confirms preorder visits the root before its children
assert post == [
    1,
    3,
    2,
    6,
    4,
]  # => confirms postorder visits the root after its children
print("ex-50 OK")  # => Output: ex-50 OK

[4, 2, 1, 3, 6]
[1, 3, 2, 6, 4]
ex-50 OK

"""Example 51: Level-Order (BFS) Traversal, Grouped by Level."""
 
from __future__ import (
    annotations,
)  # => enables forward references to the class defined below
from collections import (
    deque,
)  # => imports the stdlib double-ended queue used as the BFS frontier
 
 
class TreeNode:  # => the same binary-tree node shape as Example 48 (co-10)
    def __init__(
        self, val: int, left: TreeNode | None = None, right: TreeNode | None = None
    ) -> None:  # => constructor: stores the value plus both optional children
        self.val = val  # => the value stored at this node
        self.left = left  # => reference to the left child, or None
        self.right = right  # => reference to the right child, or None
 
 
# Breadth-first traversal, one inner list PER DEPTH LEVEL -- a deque as the
# queue gives O(1) popleft, unlike list.pop(0)'s O(n) (co-10, co-06).
def level_order(
    root: TreeNode | None,
) -> list[list[int]]:  # => a queue-driven traversal
    if root is None:  # => an empty tree has zero levels
        return []  # => nothing to traverse
    levels: list[list[int]] = []  # => one entry per depth level, in top-to-bottom order
    queue: deque[TreeNode] = deque([root])  # => FIFO queue seeded with just the root
    while queue:  # => continues until every node has been visited
        level_size = len(
            queue
        )  # => freezes "how many nodes are AT this level right now"
        current_level: list[int] = []  # => collects just this level's values
        for _ in range(level_size):  # => processes exactly this level, not the next one
            node = queue.popleft()  # => O(1): dequeue the next node at this level
            current_level.append(node.val)  # => records this node's value
            if node.left:  # => a left child exists
                queue.append(node.left)  # => enqueue it for the NEXT level
            if node.right:  # => a right child exists
                queue.append(node.right)  # => enqueue it for the NEXT level
        levels.append(current_level)  # => one finished level, added to the result
    return levels  # => the full list-of-lists, one entry per depth
 
 
#        4
#       / \
#      2   6
#     / \
#    1   3
root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(6))
levels = level_order(root)  # => groups nodes by depth: [4], [2,6], [1,3]
print(levels)  # => Output: [[4], [2, 6], [1, 3]]
 
assert levels == [
    [4],
    [2, 6],
    [1, 3],
]  # => confirms both the grouping and per-level order
print("ex-51 OK")  # => Output: ex-51 OK

[[4], [2, 6], [1, 3]]
ex-51 OK

"""Example 52: Compute Tree Height Recursively."""
 
from __future__ import (
    annotations,
)  # => enables forward references to the class defined below
 
 
class TreeNode:  # => the same binary-tree node shape as Example 48 (co-10)
    def __init__(
        self, val: int, left: TreeNode | None = None, right: TreeNode | None = None
    ) -> None:  # => constructor: stores the value plus both optional children
        self.val = val  # => the value stored at this node
        self.left = left  # => reference to the left child, or None
        self.right = right  # => reference to the right child, or None
 
 
# Height = 1 + the taller of the two child subtrees -- an empty tree has height 0 (co-10, co-17).
def height(node: TreeNode | None) -> int:  # => a plain recursive function
    if node is None:  # => BASE CASE -- no node means no height contributed
        return 0  # => the additive identity for the recursion below
    left_height = height(node.left)  # => RECURSIVE CASE: height of the left subtree
    right_height = height(node.right)  # => RECURSIVE CASE: height of the right subtree
    return 1 + max(left_height, right_height)  # => this node + whichever side is taller
 
 
#        4
#       / \
#      2   6
#     / \
#    1   3
root = TreeNode(
    4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(6)
)  # => 3 levels deep
tree_height = height(root)  # => 4 -> 2 -> 1 is the longest path, 3 nodes deep
print(tree_height)  # => Output: 3
 
assert tree_height == 3  # => confirms the height matches the deepest path's node count
assert height(None) == 0  # => confirms an empty tree has height 0
print("ex-52 OK")  # => Output: ex-52 OK

3
ex-52 OK

"""Example 53: Insert into a Binary Search Tree."""
 
from __future__ import (
    annotations,
)  # => enables forward references to the class defined below
 
 
class BSTNode:  # => an ordered binary tree: left < node < right, always (co-11)
    def __init__(self, val: int) -> None:  # => constructor: a leaf with no children yet
        self.val = val  # => the value stored at this node
        self.left: BSTNode | None = None  # => no left child yet
        self.right: BSTNode | None = None  # => no right child yet
 
 
# Descends left/right by comparison until an empty slot is found -- average O(log n) (co-11).
def insert(root: BSTNode | None, val: int) -> BSTNode:  # => a plain recursive function
    if root is None:  # => BASE CASE -- found the empty slot; this becomes a new leaf
        return BSTNode(val)  # => the newly created leaf becomes this subtree's root
    if val < root.val:  # => smaller values always go left
        root.left = insert(root.left, val)  # => recurse into the left subtree
    else:  # => equal-or-larger values always go right
        root.right = insert(root.right, val)  # => recurse into the right subtree
    return root  # => unchanged subtree root, now with the new value inserted somewhere below
 
 
# Inorder traversal of a BST always yields values in SORTED order (co-11).
def inorder(node: BSTNode | None) -> list[int]:  # => a plain recursive traversal
    if node is None:  # => BASE CASE -- nothing to visit
        return []  # => no values from this branch
    return inorder(node.left) + [node.val] + inorder(node.right)  # => left, self, right
 
 
root: BSTNode | None = None  # => starts as an empty tree
for value in (5, 2, 8, 1, 3):  # => inserts in arbitrary order
    root = insert(root, value)  # => grows the BST one value at a time
sorted_values = inorder(root)  # => the ordering PROPERTY of a BST, made visible
print(sorted_values)  # => Output: [1, 2, 3, 5, 8]
 
assert sorted_values == [1, 2, 3, 5, 8]  # => confirms inorder yields sorted order
print("ex-53 OK")  # => Output: ex-53 OK

[1, 2, 3, 5, 8]
ex-53 OK

"""Example 54: Search a Binary Search Tree."""
 
from __future__ import (
    annotations,
)  # => lets BSTNode reference "BSTNode" before fully defined
 
 
class BSTNode:  # => the same BST node shape as Example 53 (co-11)
    def __init__(self, val: int) -> None:  # => constructor: a leaf with no children yet
        self.val = val  # => the value stored at this node
        self.left: BSTNode | None = None  # => no left child yet
        self.right: BSTNode | None = None  # => no right child yet
 
 
def insert(
    root: BSTNode | None, val: int
) -> BSTNode:  # => same insert as Example 53 (co-11)
    if root is None:  # => BASE CASE -- empty slot found
        return BSTNode(val)  # => becomes the new leaf
    if val < root.val:  # => smaller values go left
        root.left = insert(root.left, val)  # => recurse left
    else:  # => equal-or-larger values go right
        root.right = insert(root.right, val)  # => recurse right
    return root  # => the (possibly updated) subtree root
 
 
# Follows the ONE branch that could contain target -- discards the other half (co-11).
def search(node: BSTNode | None, target: int) -> bool:  # => a plain recursive function
    if node is None:  # => fell off the tree without a match -- not present
        return False  # => target does not exist in this subtree
    if node.val == target:  # => found it
        return True  # => target exists at this node
    if target < node.val:  # => target must be smaller
        return search(node.left, target)  # => target can ONLY be in the left subtree
    return search(node.right, target)  # => target can ONLY be in the right subtree
 
 
root: BSTNode | None = None  # => starts as an empty tree
for value in (5, 2, 8, 1, 3):  # => builds the same BST as Example 53
    root = insert(root, value)  # => grows the BST one value at a time
 
found = search(root, 3)  # => 3 was inserted -- present
missing = search(root, 9)  # => 9 was never inserted -- absent
print(found)  # => Output: True
print(missing)  # => Output: False
 
assert found is True  # => confirms a present value is found
assert missing is False  # => confirms an absent value is correctly reported missing
print("ex-54 OK")  # => Output: ex-54 OK

True
False
ex-54 OK

"""Example 55: BST Minimum and Maximum."""
 
from __future__ import (
    annotations,
)  # => enables forward references to the class defined below
 
 
class BSTNode:  # => the same BST node shape as Example 53 (co-11)
    def __init__(self, val: int) -> None:  # => constructor: a leaf with no children yet
        self.val = val  # => the value stored at this node
        self.left: BSTNode | None = None  # => no left child yet
        self.right: BSTNode | None = None  # => no right child yet
 
 
def insert(
    root: BSTNode | None, val: int
) -> BSTNode:  # => same insert as Example 53 (co-11)
    if root is None:  # => BASE CASE -- empty slot found
        return BSTNode(val)  # => becomes the new leaf
    if val < root.val:  # => smaller values go left
        root.left = insert(root.left, val)  # => recurse left
    else:  # => equal-or-larger values go right
        root.right = insert(root.right, val)  # => recurse right
    return root  # => the (possibly updated) subtree root
 
 
# The minimum is always the LEFTMOST node -- keep walking left until it stops (co-11).
def find_min(node: BSTNode) -> int:  # => an iterative walk, no recursion needed
    while node.left is not None:  # => every left step reaches a smaller value
        node = node.left  # => keep descending left
    return node.val  # => no more left children -- this IS the smallest value
 
 
# The maximum is always the RIGHTMOST node -- keep walking right until it stops (co-11).
def find_max(node: BSTNode) -> int:  # => an iterative walk, no recursion needed
    while node.right is not None:  # => every right step reaches a larger value
        node = node.right  # => keep descending right
    return node.val  # => no more right children -- this IS the largest value
 
 
root: BSTNode | None = None  # => starts as an empty tree
for value in (5, 2, 8, 1, 3):  # => builds the same BST as Example 53
    root = insert(root, value)  # => grows the BST one value at a time
assert root is not None  # => the loop above always inserts at least one node
 
smallest = find_min(root)  # => walks left: 5 -> 2 -> 1, stops at 1
largest = find_max(root)  # => walks right: 5 -> 8, stops at 8
print(smallest, largest)  # => Output: 1 8
 
assert smallest == 1  # => confirms the leftmost node holds the true minimum
assert largest == 8  # => confirms the rightmost node holds the true maximum
print("ex-55 OK")  # => Output: ex-55 OK

1 8
ex-55 OK

"""Example 56: Build a Graph as a Dict-of-Lists Adjacency Map."""
 
# A dict-of-lists is the simplest general-purpose graph representation: each
# key is a node, each value is the list of its neighbors (co-21, co-08).
graph: dict[str, list[str]] = {  # => a 4-node, undirected-by-convention graph literal
    "a": ["b", "c"],  # => "a" connects to "b" and "c"
    "b": ["a", "d"],  # => "b" connects back to "a", plus "d"
    "c": ["a", "d"],  # => "c" connects back to "a", plus "d"
    "d": ["b", "c"],  # => "d" connects back to "b" and "c" -- a 4-node cycle
}  # => four keys total, each mapping to its own neighbor list
 
for (
    node,
    neighbors,
) in graph.items():  # => dict iteration is insertion-ordered (Python 3.7+)
    print(f"{node}: {neighbors}")  # => Output: one "node: [...]" line per graph key
 
assert graph["a"] == [
    "b",
    "c",
]  # => confirms a's neighbor list matches what was declared
assert "a" in graph["b"]  # => confirms the edge a-b is represented in BOTH directions
print("ex-56 OK")  # => Output: ex-56 OK

a: ['b', 'c']
b: ['a', 'd']
c: ['a', 'd']
d: ['b', 'c']
ex-56 OK

"""Example 57: Breadth-First Search over a Graph."""
 
# BFS explores neighbor-by-neighbor, level by level, using a deque as the
# frontier queue and a set to avoid revisiting nodes (co-21, co-05, co-09).
from collections import (
    deque,
)  # => imports the stdlib double-ended queue as the frontier
 
graph: dict[str, list[str]] = {  # => the same 4-node graph as Example 56
    "a": ["b", "c"],  # => a's neighbors
    "b": ["a", "d"],  # => b's neighbors
    "c": ["a", "d"],  # => c's neighbors
    "d": ["b", "c"],  # => d's neighbors
}  # => four keys total, each mapping to its own neighbor list
 
 
# Visits start, then all its neighbors, then all of THEIR unvisited neighbors, ...
def bfs(
    graph: dict[str, list[str]], start: str
) -> list[str]:  # => a plain BFS function
    visited: set[str] = {
        start
    }  # => tracks every node already enqueued -- O(1) membership
    order: list[str] = []  # => records the order nodes are actually VISITED (dequeued)
    queue: deque[str] = deque([start])  # => the frontier, FIFO
    while queue:  # => continues until the frontier is empty
        node = queue.popleft()  # => O(1): visit the earliest-enqueued node
        order.append(node)  # => records the visit
        for neighbor in graph[node]:  # => looks at every edge out of this node
            if neighbor not in visited:  # => O(1) average -- skip already-seen nodes
                visited.add(
                    neighbor
                )  # => mark BEFORE enqueueing to avoid duplicate enqueues
                queue.append(neighbor)  # => schedules the neighbor for a later visit
    return order  # => the full breadth-first visit order
 
 
visit_order = bfs(graph, "a")  # => a -> its neighbors b,c -> their unvisited neighbor d
print(visit_order)  # => Output: ['a', 'b', 'c', 'd']
 
assert visit_order == [
    "a",
    "b",
    "c",
    "d",
]  # => confirms the exact breadth-first visit order
assert len(visit_order) == len(graph)  # => confirms every node was visited exactly once
print("ex-57 OK")  # => Output: ex-57 OK

['a', 'b', 'c', 'd']
ex-57 OK

"""Example 58: Depth-First Search over a Graph."""
 
# DFS plunges as deep as possible down ONE path before backtracking -- the
# recursive call stack itself acts as the "stack" (co-21, co-17, co-09).
graph: dict[str, list[str]] = {  # => the same 4-node graph as Example 56
    "a": ["b", "c"],  # => a's neighbors
    "b": ["a", "d"],  # => b's neighbors
    "c": ["a", "d"],  # => c's neighbors
    "d": ["b", "c"],  # => d's neighbors
}  # => four keys total, each mapping to its own neighbor list
 
 
# Visits node, then recurses fully into the FIRST unvisited neighbor before any other.
def dfs(
    graph: dict[str, list[str]], node: str, visited: set[str], order: list[str]
) -> None:
    visited.add(node)  # => marks node as seen -- prevents infinite loops on cycles
    order.append(node)  # => records visit order for inspection
    for neighbor in graph[node]:  # => tries each neighbor in listed order
        if neighbor not in visited:  # => O(1) average membership check
            dfs(
                graph, neighbor, visited, order
            )  # => RECURSIVE CASE: plunge deeper first
 
 
visited: set[str] = (
    set()
)  # => shared across the whole traversal via the same set object
order: list[str] = []  # => shared across the whole traversal via the same list object
dfs(
    graph, "a", visited, order
)  # => a -> b (first neighbor) -> d (b's unvisited neighbor) -> c
print(order)  # => Output: ['a', 'b', 'd', 'c']
 
assert order == ["a", "b", "d", "c"]  # => confirms the exact depth-first visit order
assert visited == {"a", "b", "c", "d"}  # => confirms every node was eventually visited
print("ex-58 OK")  # => Output: ex-58 OK

['a', 'b', 'd', 'c']
ex-58 OK

"""Example 59: BFS Shortest-Path Length in an Unweighted Graph."""
 
# BFS's level-by-level nature means the FIRST time a node is reached, it was
# reached by the shortest possible number of edges -- unweighted only (co-21, co-05).
from collections import (
    deque,
)  # => imports the stdlib double-ended queue as the frontier
 
graph: dict[str, list[str]] = {  # => a 5-node graph, one edge longer than Example 57's
    "a": ["b", "c"],  # => a's neighbors
    "b": ["a", "d"],  # => b's neighbors
    "c": ["a", "d"],  # => c's neighbors
    "d": ["b", "c", "e"],  # => d's neighbors
    "e": ["d"],  # => e's only neighbor
}  # => five keys total, each mapping to its own neighbor list
 
 
# Tracks each node's distance from start, discovered in non-decreasing order via BFS.
def shortest_path_length(graph: dict[str, list[str]], start: str, end: str) -> int:
    distances: dict[str, int] = {start: 0}  # => start is 0 edges from itself
    queue: deque[str] = deque([start])  # => the frontier, FIFO
    while queue:  # => continues until the frontier is empty or end is reached
        node = queue.popleft()  # => O(1): visit the earliest-enqueued node
        if (
            node == end
        ):  # => the FIRST time end is dequeued, its distance is final and minimal
            return distances[node]  # => the shortest number of edges from start to end
        for neighbor in graph[node]:  # => looks at every edge out of this node
            if (
                neighbor not in distances
            ):  # => first discovery -- distance can only get worse later
                distances[neighbor] = (
                    distances[node] + 1
                )  # => one edge farther than node
                queue.append(neighbor)  # => schedules the neighbor for a later visit
    return -1  # => end was never reached -- no path exists (not hit in this example)
 
 
distance = shortest_path_length(
    graph, "a", "e"
)  # => a -> b/c (1 edge) -> d (2 edges) -> e (3)
print(distance)  # => Output: 3
 
assert distance == 3  # => confirms the shortest a-to-e path uses exactly 3 edges
print("ex-59 OK")  # => Output: ex-59 OK

3
ex-59 OK

"""Example 60: Maximum Sum of a Length-k Sliding Window."""
 
 
# Slides a fixed-size window, updating the sum incrementally -- O(n),
# instead of re-summing each window from scratch, which would be O(n*k) (co-20).
def max_window_sum(
    values: list[int], k: int
) -> int:  # => a plain sliding-window function
    window_sum = sum(values[:k])  # => O(k): the sum of the FIRST window only
    best = window_sum  # => tracks the best sum seen so far
    for i in range(k, len(values)):  # => slides the window one element at a time
        window_sum += (
            values[i] - values[i - k]
        )  # => add the new element, drop the old one
        # => this single O(1) update replaces re-summing k elements from scratch
        best = max(best, window_sum)  # => keep the running maximum
    return best  # => the maximum window sum found across every position
 
 
numbers = [2, 1, 5, 1, 3, 2]  # => 6 values; window size 3
result = max_window_sum(
    numbers, 3
)  # => windows: [2,1,5]=8, [1,5,1]=7, [5,1,3]=9, [1,3,2]=6
print(result)  # => Output: 9
 
assert result == 9  # => confirms the best window (index 2..4: 5+1+3) was found
print("ex-60 OK")  # => Output: ex-60 OK

9
ex-60 OK