Unit 4: Recursion and Trees

I. Orientation

Recursion solves a problem by applying the same method to smaller instances, while trees organize data hierarchically through parent-child relationships. Together, they support searching, traversal, sorting, and divide-and-conquer algorithms.

• Defining properties:
  • Base case: Stops recursive calls at a directly solvable instance.
  • Recursive case: Reduces the current problem toward the base case.
  • Call stack: Stores parameters, local variables, and return addresses for active calls.
  • Tree hierarchy: Begins at a root and connects nodes through edges.
  • Recursive structure: Each subtree is itself a tree, making recursive processing natural.
• Conventions:
  • NULL denotes a missing child link.
  • Tree height is measured here as the number of edges on the longest root-to-leaf path.
  • For complexity, n is the number of elements and h is tree height.

II. Recursion — Self-Referential Problem Solving

Recursion is a technique in which a function calls itself, directly or indirectly, to solve progressively smaller versions of a problem.

A. Introduction to recursion

A correct recursive algorithm must have a reachable base case and must reduce the problem on every recursive call.

• General form:

function solve(problem):
    if problem is simple enough:
        return direct_solution
    return combine(solve(smaller_problem))

• Execution: Each call creates a stack frame; returns occur in reverse order, following last-in, first-out behavior.
• Example: Factorial is defined by n! = n × (n−1)!, with 0! = 1.

factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

• Complexity: factorial(n) makes n + 1 calls, requiring O(n) time and O(n) stack space.
• Risks: A missing base case causes infinite recursion; excessive depth can cause stack overflow.
• Comparison with iteration: Recursion often expresses trees and divide-and-conquer algorithms clearly, while loops usually avoid call-stack overhead.

III. Binary-Tree Structures — Hierarchical Data Models

A binary tree is either empty or consists of a root and two disjoint binary trees called the left and right subtrees.

A. Binary trees

A binary tree restricts each node to at most two ordered children.

• Terminology:
  • Root: Topmost node.
  • Leaf: Node with no children.
  • Internal node: Node with at least one child.
  • Degree: Number of children of a node, from 0 to 2.
  • Depth: Number of edges from the root to a node.
• Capacity: Level d contains at most 2^d nodes; a tree of height h contains at most 2^(h+1) − 1 nodes.
• Uses: Expression trees, decision trees, search trees, heaps, and hierarchical indexing.

B. Complete binary trees

A complete binary tree has every level full except possibly the last, whose nodes occupy the leftmost positions.

• Shape condition: No position on the last level may be skipped before a later position is occupied.
• Height: A complete tree with n nodes has height ⌊log₂ n⌋.
• Benefit: Its compact shape supports efficient array storage without internal gaps.
• Distinction: A perfect binary tree has all internal nodes with two children and all leaves at one level; completeness does not require the last level to be full.

C. Extended binary trees

An extended binary tree replaces every missing child of an ordinary binary tree with a special external node.

• Node classes:
  1. Internal nodes: Original data-bearing nodes.
  2. External nodes: Added placeholders representing NULL links.
• Property: Every internal node has exactly two children in the extended representation.
• Counting relation: If there are I internal nodes, there are E = I + 1 external nodes.
• Use: External nodes simplify structural proofs and analysis of unsuccessful binary-search-tree searches.

D. Linked memory representation of binary trees

Linked representation stores each node separately and uses pointers to connect it to its children.

• Node layout:

Node:
    data
    left   // pointer to left child
    right  // pointer to right child

• Root pointer: Identifies the tree; an empty tree has root = NULL.
• Advantages: Supports irregular trees and dynamic insertion or deletion without shifting unrelated nodes.
• Cost: Two pointer fields consume extra memory, and separately allocated nodes may have poor cache locality.
• Leaf encoding: For a leaf node, both left and right equal NULL.

E. Sequential memory representation of binary trees

Sequential representation stores nodes in an array according to their structural positions.

• Zero-based relationships: For a node at index i, the left child is at 2i + 1, the right child at 2i + 2, and the parent at ⌊(i−1)/2⌋.
• Example: The children of index 3 occupy indices 7 and 8.
• Strength: Complete trees use contiguous memory efficiently and permit constant-time parent-child index calculations.
• Limitation: A sparse or skewed tree leaves many unused array positions.
• Application: Binary heaps commonly use this representation.

IV. Binary Search Trees — Ordered Dynamic Sets

A binary search tree, or BST, is a binary tree whose ordering enables navigation based on key comparisons.

A. Introduction to binary search trees

A BST maintains an ordering invariant at every node.

• Invariant: All keys in the left subtree are smaller than the node’s key, and all keys in the right subtree are larger, assuming distinct keys.
• Duplicate policy: Implementations must consistently reject duplicates, count them, or place them on a designated side.
• Order result: In-order traversal produces keys in ascending order.
• Performance: Operations take O(h) time; this is O(log n) for a balanced tree but O(n) for a skewed tree.

B. Binary search tree searching

BST search compares the target with one node and discards one subtree at each step.

• Procedure:

search(node, key):
    if node == NULL or node.key == key:
        return node
    if key < node.key:
        return search(node.left, key)
    return search(node.right, key)

• Decision rule: A smaller target moves left; a larger target moves right.
• Termination: Finding the key succeeds; reaching NULL means the key is absent.
• Complexity: Time is O(h) and recursive auxiliary space is O(h).

C. Binary search tree insertion

Insertion searches for a missing child position while preserving the BST invariant.

• Procedure:

insert(node, key):
    if node == NULL:
        return new Node(key)
    if key < node.key:
        node.left = insert(node.left, key)
    else if key > node.key:
        node.right = insert(node.right, key)
    return node

• Placement: The new node is always created as a leaf.
• Example: Inserting 6 into a tree rooted at 8, with left child 3, follows 8 → 3 and then enters the appropriate right-subtree position.
• Complexity: Insertion requires O(h) time and preserves existing node order.

D. Binary search tree deletion

BST deletion removes a key while reconnecting nodes so that ordering remains valid.

• Cases:
  1. Leaf: Remove the node and replace its parent link with NULL.
  2. One child: Replace the node with its only child.
  3. Two children: Copy the in-order successor, the minimum key in the right subtree, then delete that successor.
• Successor reason: The smallest right-subtree key is greater than every key in the left subtree and no greater than the remaining right-subtree keys.
• Complexity: Searching and restructuring take O(h) time.
• Critical detail: Deleting the root may change the root pointer, so the operation should return the updated subtree root.

V. Recursive Tree Traversals — Systematic Node Visits

A traversal visits every node exactly once; the order of processing the root distinguishes the three standard depth-first traversals.

A. In-order traversal using recursion

In-order traversal visits the left subtree, the root, and then the right subtree.

inorder(node):
    if node != NULL:
        inorder(node.left)
        visit(node)
        inorder(node.right)

• Order: Left–Root–Right, abbreviated LNR.
• BST significance: It lists BST keys in nondecreasing order.
• Complexity: Visits n nodes in O(n) time and uses O(h) stack space.

B. Pre-order traversal using recursion

Pre-order traversal processes the root before either subtree.

preorder(node):
    if node != NULL:
        visit(node)
        preorder(node.left)
        preorder(node.right)

• Order: Root–Left–Right, abbreviated NLR.
• Applications: Copying a tree, serializing structure with null markers, and generating prefix expressions.
• Complexity: Time is O(n) and recursive space is O(h).

C. Post-order traversal using recursion

Post-order traversal processes the root only after both subtrees.

postorder(node):
    if node != NULL:
        postorder(node.left)
        postorder(node.right)
        visit(node)

• Order: Left–Right–Root, abbreviated LRN.
• Applications: Deleting an entire tree safely and evaluating expression trees from operands upward.
• Complexity: Time is O(n) and stack space is O(h).

VI. Towers of Hanoi — Recursive Decomposition

The Towers of Hanoi problem moves disks between three pegs while never placing a larger disk above a smaller one.

A. Recursive implementation of Towers of Hanoi

The solution moves n−1 disks aside, moves the largest disk, and then restores the smaller disks above it.

hanoi(n, source, auxiliary, destination):
    if n == 1:
        move source to destination
        return
    hanoi(n - 1, source, destination, auxiliary)
    move source to destination
    hanoi(n - 1, auxiliary, source, destination)

• Rules: Move one disk at a time; only the top disk may move; a larger disk cannot cover a smaller disk.
• Recurrence: T(n) = 2T(n−1) + 1, with T(1) = 1.
• Minimum moves: Solving the recurrence gives T(n) = 2^n − 1; three disks require seven moves.
• Complexity: Time is O(2^n) and recursion depth is O(n).

VII. Merge Sort — Divide, Sort, and Merge

Merge sort recursively sorts two halves and combines them into one ordered sequence.

A. Merge sort

Merge sort divides until subarrays have at most one element, then merges sorted subarrays.

mergeSort(A, left, right):
    if left >= right:
        return
    mid = floor((left + right) / 2)
    mergeSort(A, left, mid)
    mergeSort(A, mid + 1, right)
    merge(A, left, mid, right)

• Merge step: Compare the first unconsumed items of both halves, copy the smaller one, and finally copy any remainder.
• Recurrence: T(n) = 2T(n/2) + Θ(n), yielding Θ(n log n) time.
• Space: Standard array merging requires Θ(n) auxiliary storage.
• Properties: Merge sort is stable when equal elements from the left half are selected first.
• Use: It performs predictably on linked lists and external data stored across files.

VIII. Quick Sort — Partition-Based Sorting

Quick sort selects a pivot, partitions elements around it, and recursively sorts the resulting regions.

A. Quick sort

Quick sort places a pivot in its final ordered position or creates partitions whose keys lie on the correct side of the pivot.

quickSort(A, low, high):
    if low < high:
        p = partition(A, low, high)
        quickSort(A, low, p - 1)
        quickSort(A, p + 1, high)

• Partitioning: A Lomuto-style partition may choose A[high] as pivot, move values ≤ pivot left, and return pivot index p.
• Average behavior: Reasonably balanced partitions give Θ(n log n) time.
• Worst case: Repeated partitions of sizes 0 and n−1 produce Θ(n²) time, as can occur with poor pivot choices on ordered input.
• Space: Recursive stack usage is O(log n) on average and O(n) in the worst case.
• Properties: Typical implementations are in-place but unstable; randomized or median-based pivot selection reduces the likelihood of severe imbalance.