Binary Trees — Recap

A binary tree is a rooted tree where each node has at most two children: left and right. A Binary Search Tree (BST) additionally enforces: left child < parent < right child. Tree traversal visits all nodes systematically — three DFS-based orders are used.

Example tree used throughout:

        4
       / \
      2   6
     / \ / \
    1  3 5  7

Pre-Order Traversal (Root → Left → Right)

Visit the current node FIRST, then traverse the left subtree, then the right subtree. Produces a top-down view. Used for copying/serialising a tree.

function preOrder(node)
    if node = None then return
    process(node)              // Visit ROOT first
    preOrder(node.left)        // Then LEFT
    preOrder(node.right)       // Then RIGHT
endfunction

Pre-order on example tree: 4, 2, 1, 3, 6, 5, 7

Mnemonic: R-L-R (Root, Left, Right) — "Pre" = root first (pre-fix notation)

In-Order Traversal (Left → Root → Right)

Traverse the left subtree, then visit the current node, then traverse the right subtree. Visits nodes in sorted ascending order for a BST — used for BST sorting and displaying values in order.

function inOrder(node)
    if node = None then return
    inOrder(node.left)         // LEFT first
    process(node)              // Then ROOT
    inOrder(node.right)        // Then RIGHT
endfunction

In-order on example tree: 1, 2, 3, 4, 5, 6, 7 (sorted!)

Mnemonic: L-R-R (Left, Root, Right) — "In" = root in-between

Post-Order Traversal (Left → Right → Root)

Traverse left subtree, then right subtree, then visit the current node LAST. Used for deleting a tree (children before parents) and evaluating expression trees (leaves before operators).

function postOrder(node)
    if node = None then return
    postOrder(node.left)       // LEFT first
    postOrder(node.right)      // Then RIGHT
    process(node)              // ROOT last
endfunction

Post-order on example tree: 1, 3, 2, 5, 7, 6, 4

Mnemonic: L-R-R (Left, Right, Root) — "Post" = root last (post-fix notation)

Summary of Tree Traversals

Dijkstra's Shortest Path Algorithm

Dijkstra's algorithm finds the shortest path from a single source to all other vertices in a weighted graph with non-negative edge weights. It is a greedy algorithm — always processes the vertex with the currently smallest known distance.

Algorithm

function dijkstra(graph, source)
    dist ← dictionary, all vertices = ∞
    dist[source] ← 0
    prev ← dictionary (to reconstruct path)
    unvisited ← priority queue of (distance, vertex)
    enqueue (0, source) to unvisited

    while unvisited not empty
        (d, u) ← dequeue minimum from unvisited    // greedy choice
        for each neighbour v of u with edge weight w
            alt ← dist[u] + w
            if alt < dist[v] then        // found shorter path
                dist[v] ← alt
                prev[v] ← u
                enqueue (alt, v) to unvisited
            endif
        next v
    endwhile
    return dist, prev
endfunction

Worked Example

Graph: A→B(4), A→C(2), C→B(1), B→D(5), C→D(8), B→E(3), D→E(2)

Shortest paths from A: to B=3 (A→C→B), C=2, D=8 (A→C→B→D), E=6 (A→C→B→E)

Complexity

Why Dijkstra's is Greedy

At each step, Dijkstra's processes the vertex with the minimum tentative distance — the locally optimal (greedy) choice. Because all edge weights are non-negative, once a vertex is processed its distance is final — no shorter path can be found later. This greedy property is proven by induction and relies on non-negative weights (with negative weights, a processed vertex's distance might be improved later, breaking the algorithm).