2.3.1 - Data-structure algorithms and tree traversal

Preserve stack and queue order when changing state

A stack removes the most recently added item: last in, first out. A queue removes the earliest remaining item: first in, first out. These are logical rules; using an array underneath does not change them.

For a fixed array stack of capacity C, let count be the number of stored items, initially 0. Live items occupy indices 0 to count-1, with the top at count-1. The following pseudocode rejects overflow/underflow without changing state. Stack and count are shared state; ERROR ends the operation.

procedure push(value)
    if count == C then
        ERROR "full"
    endif
    stack[count] = value
    count = count + 1
endprocedure

function pop()
    if count == 0 then
        ERROR "empty"
    endif
    count = count - 1
    return stack[count]
endfunction

Push 4, push 9, pop returns 9 and leaves count = 1. Old bytes at the removed position need not be erased to remove the item logically: count determines membership. In an object implementation, releasing an unused reference can also avoid retaining unnecessary memory.

A circular array queue avoids shifting every remaining item on removal. Let front identify the next item to remove, rear identify the next free insertion slot, and count distinguish empty from full. Initially front = rear = count = 0; C must be positive.

procedure enqueue(value)
    if count == C then
        ERROR "full"
    endif
    queue[rear] = value
    rear = (rear + 1) MOD C
    count = count + 1
endprocedure

function dequeue()
    if count == 0 then
        ERROR "empty"
    endif
    value = queue[front]
    front = (front + 1) MOD C
    count = count - 1
    return value
endfunction

With C = 3, enqueue A,B,C makes rear = 0 again but count = 3, so it is full. Dequeue returns A and advances front to 1. Enqueue D fills slot 0; removal order is now B,C,D even though physical array order is D,B,C. Modulo wraps indices; count resolves the otherwise ambiguous front = rear state.

Under a fixed-size-value and constant indexed-access model, each shown operation changes a fixed number of fields, so it takes constant work. A queue implemented by shifting n remaining elements instead takes linear work per removal. Cost belongs to the implementation, not just the abstract structure name.

Reconnect links before detaching a list node

A singly linked list stores a value and a next reference in each node. Head references the first node; a null reference ends the list. The node links, rather than physical memory order, determine the sequence.

To insert at the head, allocate new, set new.next = head, then set head = new. That order retains access to the old list. To insert after a known node p, first set new.next = p.next, then p.next = new. Setting p.next first and then copying it into new.next can accidentally create a self-link and lose the old successor.

Deleting the first node whose value equals target uses current and previous references. Start current = head and previous = null. While current is not null, compare its value. On a match, if previous is null set head = current.next; otherwise set previous.next = current.next. Then stop and return the new head. On a failure set previous = current, then current = current.next. Reaching null means no change. Free or release the detached node only after repairing the links.

For head → 14 → 28 → 35 → null, deleting 28 makes the 14 node's next reference point to 35. Deleting 14 instead changes head to 28. Deleting the only node makes head null. With duplicates, this contract deletes only the first match; removing all matches needs a different continuation rule.

Locating a value can require scanning all n nodes. Once a predecessor or insertion position is already known, changing these fixed links is constant work. A statement that linked-list deletion is always constant-time hides the possible search. An array of node records can implement the same links using indices and a null sentinel; freed slots must be managed without shifting records and invalidating links.

Use ordering for search and retain subtrees on deletion

A binary search tree (BST) stores smaller keys throughout a node's left subtree and larger keys throughout its right subtree. This lesson uses unique integer keys and ignores duplicate insertions. A node has fields key, left and right; an absent child or empty root is None in Python.

To search, start at root: equality succeeds, a smaller target follows left, and a larger target follows right. An absent reference ends an unsuccessful search. To insert, follow those same comparisons until an absent child position, then attach a new leaf. An empty tree needs its root set. In a valid finite tree each move descends a level, so the procedure terminates.

For root 42, left child 21 and right child 70, with 55 as 70's left child, inserting 60 compares 42 → 70 → 55 then attaches 60 as 55's right child. It satisfies both 60 > 55 and the ancestor requirement 60 < 70.

Deletion first locates the key. A leaf can be detached. A node with one child is replaced in its parent's link by that child; deleting root changes root. For two children, copy the key and payload of the inorder successor—the smallest node in the right subtree—then remove that successor from its old position, reconnecting its possible right child. The predecessor, largest in the left subtree, is an equally valid alternative. Do not discard the surviving descendant links.

Delete 42 from the example after inserting 60. Successor 55 becomes the root key; 70's left link becomes 60. The remaining keys are 21,55,60,70. A general multi-child tree has no BST ordering rule: deletion might remove an entire subtree or promote children, depending on its explicit contract. Traversal can handle either shape, but key-based branch elimination requires ordering.

Search, insertion and deletion paths depend on height h. A balanced shape gives logarithmic path length; a chain gives linear length. The ordinary insertion procedure does not rebalance the tree. Binary means at most two children, not guaranteed halving.

Complete each subtree before processing its parent

The postorder rule applies inside every subtree. A null subtree produces no output. Recursion supplies a stack of unfinished calls, and returning from a child resumes its parent: this is backtracking.

Use this exact binary tree for the worked traversals:

Postorder on the left subtree outputs 10,30,20. Postorder on the right outputs 50,70,60. Only then output root 40. The full result is 10,30,20,50,70,60,40. Descending to root 40 first does not mean outputting it first.

def postorder(root):
    result = []

    def visit(current):
        if current is None:
            return
        visit(current["left"])
        visit(current["right"])
        result.append(current["key"])

    visit(root)
    return result

The returned collection is created once; each call has its own current reference. Moving append above both recursive calls would produce preorder. Moving it between them would produce inorder. Only inorder gives ascending keys for a valid unique-key BST; postorder does not sort them. For a general tree with ordered children, postorder recursively processes every child in that order before its parent.