Unit 4: Recursion and Trees - Subjective Questions

Recursion is a programming technique in which a function solves a problem by calling itself with a smaller or simpler instance of the same problem.

A recursive algorithm has two essential components:

• Base case: The condition under which the function returns a result without making another recursive call. It prevents infinite recursion.
• Recursive case: The part that reduces the original problem and calls the function again.

For example, factorial is defined as:

A recursive implementation is:

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

For factorial(4), the calls are factorial(4), factorial(3), factorial(2), factorial(1), and factorial(0). The results are then returned in reverse order. Each call occupies an activation record on the call stack, so the space complexity is .

Whenever a recursive function is called, the system creates an activation record or stack frame containing:

• Function parameters
• Local variables
• Return address
• Saved execution state

The frame is pushed onto the call stack. When a base case is reached, calls begin returning, and the frames are popped in last-in, first-out order.

Advantages of recursion:

• Produces concise solutions for naturally recursive structures such as trees.
• Simplifies divide-and-conquer algorithms such as merge sort and quick sort.
• Makes backtracking and mathematical recurrence problems easier to express.

Limitations of recursion:

• Every call consumes stack memory.
• Excessive recursion may cause stack overflow.
• Function-call overhead may make recursion slower than iteration.
• An incorrect or unreachable base case causes infinite recursion.
• Recursive execution can be harder to trace and debug.

Recursion is most appropriate when each call substantially reduces the problem and the recursive formulation is clearer than an equivalent iterative solution.

A binary tree is a finite set of nodes that is either empty or consists of a root node and two disjoint binary trees called the left subtree and right subtree. Each node can have at most two children.

Important terminology includes:

• Root: The topmost node of the tree.
• Parent: A node that has one or more children.
• Child: A node directly connected below another node.
• Leaf node: A node having no children.
• Internal node: A node having at least one child.
• Sibling nodes: Nodes having the same parent.
• Ancestor and descendant: Nodes occurring above or below another node, respectively.
• Degree of a node: Number of children of that node; in a binary tree it is , , or .
• Depth of a node: Number of edges from the root to that node.
• Height of a node: Number of edges on the longest path from that node to a leaf.
• Height of a tree: Height of its root.
• Subtree: A node together with all of its descendants.

At level , a binary tree can contain at most nodes when the root is considered to be at level .

A complete binary tree is a binary tree in which every level except possibly the last is completely filled, and the nodes at the last level are placed as far left as possible.

For a complete binary tree containing nodes and using zero-based levels:

• The height is .
• The minimum possible number of nodes for height is .
• The maximum possible number of nodes for height is:

When stored sequentially in a zero-based array, for a node at index :

• Left child index:
• Right child index:
• Parent index: , for

The leaf nodes occupy indices from through . Therefore, the number of leaves is , while the number of non-leaf nodes is .

Because nodes occupy consecutive array positions, a complete binary tree is particularly suitable for sequential representation and is used in binary heaps.

An extended binary tree, also called a 2-tree or full binary tree representation, is obtained by replacing every missing left or right child of an ordinary binary tree with a special external node.

The conversion process is:

• Retain every original node as an internal node.
• If an internal node has no left child, attach an external node as its left child.
• If it has no right child, attach an external node as its right child.
• After conversion, every internal node has exactly two children.

If the number of internal nodes is and the number of external nodes is , then:

Therefore, the total number of nodes is:

Extended binary trees are useful because they explicitly represent null links and simplify the analysis of binary trees, search trees, prefix codes, and traversal algorithms. External nodes do not contain ordinary application data; they indicate the absence of a subtree.

In linked representation, every binary-tree node is stored as a separate record containing three fields:

• data: stores the value associated with the node.
• left: stores a reference to the root of the left subtree.
• right: stores a reference to the root of the right subtree.

A typical node can be represented as:

Node:
    data
    left
    right

A separate pointer named root refers to the root node. For an empty tree, root is null. If a child is absent, the corresponding link is also null.

Characteristics:

• Nodes need not occupy consecutive memory locations.
• The tree can grow or shrink dynamically.
• Insertion and deletion mainly require link adjustments.
• No array positions are wasted for absent nodes.
• Additional memory is required for two links in every node.
• Access to a child is direct, but random access by position is not available.

Linked representation is suitable for binary search trees and irregular or sparse binary trees because memory is allocated only for nodes that actually exist.

In sequential representation, the nodes of a binary tree are stored in an array. The root is stored first, followed by nodes level by level from left to right.

For zero-based indexing, if a node is stored at index :

• Left child is at .
• Right child is at .
• Parent is at for .

For one-based indexing, if a node is stored at position :

• Left child is at .
• Right child is at .
• Parent is at .

Advantages:

• Parent and child positions can be computed directly.
• No pointer fields are required.
• Storage has good cache locality.
• It is efficient for complete or nearly complete binary trees.

Disadvantages:

• Sparse or skewed trees may leave many unused array positions.
• A fixed-size array limits growth, while resizing can be expensive.
• Insertions that must preserve a particular array order may require extra work.

This representation is commonly used for complete binary trees, especially binary heaps.

Linked representation:

• Stores each node in a dynamically allocated record.
• Uses explicit left and right links.
• Does not require consecutive memory locations.
• Efficiently represents sparse, skewed, and dynamically changing trees.
• Requires extra memory for links.
• Has weaker cache locality and does not support direct index-based access.

Sequential representation:

• Stores nodes in an array, generally in level order.
• Computes relationships using index formulas.
• Does not require child-pointer fields.
• Provides good cache locality and direct positional access.
• Is highly space-efficient for complete binary trees.
• Wastes memory when the tree is sparse or highly skewed.
• May require resizing when the array becomes full.

Thus, sequential representation is preferred for complete binary trees such as heaps, whereas linked representation is preferred for binary search trees and other trees whose shapes change dynamically.

A binary search tree, or BST, is a binary tree in which, for every node with key :

• Every key in its left subtree is less than .
• Every key in its right subtree is greater than .
• Both subtrees are themselves binary search trees.

If duplicate keys are permitted, the implementation must use a consistent policy, such as storing duplicates on one fixed side or maintaining a count in each node.

Major BST operations include:

• Searching for a key
• Inserting a key
• Deleting a key
• Finding the minimum or maximum
• Finding a predecessor or successor
• Traversing keys in sorted order

The cost of search, insertion, and deletion is proportional to the tree height , so each operation takes time.

• In a balanced BST, .
• In the worst case, a BST may become skewed, giving .

An in-order traversal of a BST visits its keys in ascending order.

BST search compares the required key with the key at the current node:

• If the current node is null, the key is absent.
• If the keys are equal, the search succeeds.
• If the required key is smaller, search the left subtree.
• If it is larger, search the right subtree.

Recursive pseudocode:

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)

Only one subtree is searched after each comparison. Therefore, the time complexity is , where is the tree height.

• Balanced-tree case:
• Worst-case skewed tree:

The recursive auxiliary space is also because each recursive call creates a stack frame. An iterative version performs the same comparisons but uses auxiliary space.

To insert a key into a BST, begin at the root and compare the key with each visited node. Move left for a smaller key and right for a larger key until a null link is found. The new node is placed at that link.

Recursive pseudocode:

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

For 50, 30, 70, 20, 40, 60, 80, the resulting tree is:

    50
   /  \
  30   70
 / \   / \
20 40 60 80

The BST property is preserved after every insertion. The time complexity is per insertion, where is the tree height. It is for a balanced tree and for a skewed tree. The algorithm must also define how duplicate keys are handled.

Deletion begins by searching for the node containing the key. After it is found, one of three cases applies:

• Leaf node: Remove the node and set its parent's corresponding link to null.
• Node with one child: Replace the node with its only child.
• Node with two children: Replace its key with its in-order successor, which is the smallest key in the right subtree, and then delete that successor. The in-order predecessor may be used instead.

Recursive pseudocode:

delete(node, key):
    if node == null:
        return null
    if key < node.key:
        node.left = delete(node.left, key)
    else if key > node.key:
        node.right = delete(node.right, key)
    else:
        if node.left == null:
            return node.right
        if node.right == null:
            return node.left
        successor = minimum(node.right)
        node.key = successor.key
        node.right = delete(node.right, successor.key)
    return node

The operation takes time and recursive stack space. For balanced trees this is , while for a skewed tree it is . Reconnecting the returned subtree roots is essential for preserving the tree after deletion.

In-order traversal visits a binary tree in the order:

Left subtree, Root, Right subtree

Recursive pseudocode:

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

For the tree with root 50, left child 30, right child 70, and leaves 20, 40, 60, 80, the output is:

20, 30, 40, 50, 60, 70, 80

Important applications include:

• Producing keys of a BST in ascending order
• Evaluating or displaying infix expressions from expression trees
• Copying or processing nodes according to sorted BST order

Every node is visited exactly once, so the time complexity is . The auxiliary stack space is , where is the tree height. It becomes for a balanced tree and for a skewed tree.

Pre-order traversal visits a binary tree in the order:

Root, Left subtree, Right subtree

Recursive pseudocode:

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

For the tree with root 50, left subtree rooted at 30, and right subtree rooted at 70, the traversal is:

50, 30, 20, 40, 70, 60, 80

Applications include:

• Creating a copy of a tree when combined with structural information
• Generating prefix notation from an expression tree
• Serializing a tree when null markers are included
• Processing a parent before processing its descendants

Each node is visited once, giving time complexity. The recursive stack requires auxiliary space, where is the height of the tree.

Post-order traversal visits a binary tree in the order:

Left subtree, Right subtree, Root

Recursive pseudocode:

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

For the tree with root 50, left subtree rooted at 30, and right subtree rooted at 70, the traversal is:

20, 40, 30, 60, 80, 70, 50

Applications include:

• Deleting or freeing an entire tree because children are processed before their parent
• Evaluating expression trees
• Producing postfix expressions
• Computing properties that depend on both subtrees, such as height

Every node is visited exactly once, so the time complexity is . The recursive auxiliary space is , where is the tree height.

The three depth-first traversals differ in the point at which the root is visited:

• In-order: Left, Root, Right
• Pre-order: Root, Left, Right
• Post-order: Left, Right, Root

The given tree is:

    A
   / \
  B   C
 / \   \
D   E   F

The traversal sequences are:

• In-order: D, B, E, A, C, F
• Pre-order: A, B, D, E, C, F
• Post-order: D, E, B, F, C, A

Typical uses:

• In-order gives sorted output for a BST.
• Pre-order is useful for prefix expressions and root-first serialization.
• Post-order is useful for postfix expressions and safe tree deletion.

All three traversals visit every node once and therefore require time. Their recursive stack usage is .

The Towers of Hanoi problem has three pegs: source, auxiliary, and destination. The objective is to move disks from the source peg to the destination peg under these rules:

• Move only one disk at a time.
• Move only the top disk of a peg.
• Never place a larger disk on a smaller disk.

The recursive strategy is:

1. Move the top disks from source to auxiliary.
2. Move the largest disk from source to destination.
3. Move the disks from auxiliary to destination.

Pseudocode:

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)

If is the number of moves, then:

Expanding the recurrence gives:

Thus, the minimum number of moves is , the time complexity is , and the recursion stack requires space.

Merge sort is a recursive divide-and-conquer sorting algorithm.

Its three phases are:

• Divide: Split the array into two approximately equal halves.
• Conquer: Recursively sort both halves.
• Combine: Merge the sorted halves into one sorted array.

Pseudocode:

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

The merge operation compares the first unprocessed elements of the two halves and repeatedly copies the smaller one into a temporary array.

The recurrence is:

At each of levels, merging requires work. Therefore:

Characteristics:

• Best, average, and worst-case time:
• Auxiliary array space:
• Recursive stack space:
• Stable when equal elements are merged in their original order
• Well suited to linked lists and external sorting
• Generally not an in-place array sort

Quick sort is a recursive divide-and-conquer algorithm that selects a pivot and partitions the array so that smaller elements are placed before the pivot and larger elements after it.

Using a Lomuto-style partition:

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

partition(A, low, high):
    pivot = A[high]
    i = low - 1
    for j = low to high - 1:
        if A[j] <= pivot:
            i = i + 1
            swap A[i], A[j]
    swap A[i + 1], A[high]
    return i + 1

For balanced partitions, the recurrence is:

For highly unbalanced partitions:

Therefore:

• Best case:
• Average case:
• Worst case:

Quick sort is usually in-place apart from recursion, is generally not stable, and often performs well in practice due to good cache locality. Randomized or median-based pivot selection reduces the chance of worst-case partitions.

Both algorithms use divide and conquer, but they perform their main work at different stages.

Merge sort:

• Divides the input into equal halves before recursive sorting.
• Performs most work while merging sorted halves.
• Has time in the best, average, and worst cases.
• Requires auxiliary space for typical array implementations.
• Is stable when implemented appropriately.
• Works well for linked lists and external sorting.
• Has predictable performance regardless of initial order.

Quick sort:

• Partitions the input around a pivot before recursive sorting.
• Performs most work during partitioning.
• Has average and best-case time .
• Has worst-case time .
• Usually needs only recursive stack space: on average and in the worst case.
• Is generally not stable.
• Often sorts arrays faster in practice because of locality and low constant factors.

Merge sort is preferable when stability or guaranteed worst-case performance is required. Quick sort is often preferable for in-memory arrays when average performance and low additional storage are priorities.