Stack in Recursion, Stack Operations, and Infix to Postfix Conversion

1. How Stack is Used in Recursion (2 marks)

When a recursive function is called, the system uses an internal data structure called the call stack (or system stack) to manage function calls.

Mechanism:

• Every time a function calls itself recursively, the current state (local variables, parameters, and return address) is pushed onto the stack.
• When the base case is reached, the function returns and the saved state is popped from the stack, resuming execution from where it left off.
• This continues until the stack is empty and the original call completes.

Example: Factorial of n

factorial(3)
  → calls factorial(2)   [state of factorial(3) pushed]
    → calls factorial(1) [state of factorial(2) pushed]
      → returns 1        [base case]
    ← factorial(2) = 2×1 = 2  [popped]
  ← factorial(3) = 3×2 = 6   [popped]

Stack at deepest point:

Stack follows LIFO (Last In First Out) which perfectly models the "last called, first returned" nature of recursion.

2. Stack Operations (3 marks)

A stack is a linear data structure that follows the LIFO principle. The main operations are:

a) PUSH (Insert an element)

Adds an element to the top of the stack.

Algorithm:

PUSH(STACK, TOP, MAXSIZE, ITEM):
1. If TOP = MAXSIZE - 1, then:
      Print "Stack Overflow" and Return
2. Set TOP = TOP + 1
3. Set STACK[TOP] = ITEM
4. Return

b) POP (Delete an element)

Removes and returns the element from the top of the stack.

Algorithm:

POP(STACK, TOP):
1. If TOP = -1, then:
      Print "Stack Underflow" and Return
2. Set ITEM = STACK[TOP]
3. Set TOP = TOP - 1
4. Return ITEM

c) PEEK / TOP

Returns the top element without removing it.

PEEK(STACK, TOP):
1. If TOP = -1, then:
      Print "Stack is Empty" and Return
2. Return STACK[TOP]

d) isEmpty

Checks whether the stack is empty.

isEmpty(STACK, TOP):
1. If TOP = -1, Return TRUE
2. Else Return FALSE

e) isFull

Checks whether the stack is full.

isFull(STACK, TOP, MAXSIZE):
1. If TOP = MAXSIZE - 1, Return TRUE
2. Else Return FALSE

3. Algorithm to Convert Infix to Postfix Using Stack (5 marks)

Key Concepts

Operator Precedence Table

Algorithm: Infix to Postfix

InfixToPostfix(expression):

1. Initialize an empty STACK and empty output string POSTFIX.
2. Scan the infix expression from LEFT to RIGHT, one token at a time.
3. For each token:

   a. If token is an OPERAND (letter or digit):
         Append it directly to POSTFIX.

   b. If token is '(' (left parenthesis):
         PUSH it onto STACK.

   c. If token is ')' (right parenthesis):
         While TOP of STACK ≠ '(':
            POP from STACK and append to POSTFIX.
         POP '(' from STACK (discard it).

   d. If token is an OPERATOR (+, -, *, /, ^):
         While STACK is not empty AND
               precedence(TOP of STACK) >= precedence(token):
            POP from STACK and append to POSTFIX.
         PUSH the current token onto STACK.

4. After all tokens are scanned:
      While STACK is not empty:
         POP from STACK and append to POSTFIX.

5. Return POSTFIX.

Worked Example

Convert: A + B * C - D

Result: A B C * + D -

Another Example with Parentheses

Convert: (A + B) * C

Applications of Binary Tree

Applications of Binary Tree

A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child. Binary trees have numerous important applications in computer science.

1. Binary Search Tree (BST)

• A binary tree is used to implement BST, where the left subtree contains nodes with values less than the root and the right subtree contains nodes with values greater than the root.
• Used for efficient searching, insertion, and deletion of data in O(log n) time.
• Example: Dictionary implementations, database indexing.

2. Expression Tree

• Binary trees are used to represent arithmetic expressions.
• Leaf nodes store operands (numbers/variables) and internal nodes store operators (+, -, *, /).
• Used in compilers to evaluate and parse mathematical expressions.
• Example: Expression (a + b) * c can be represented as a binary tree.

3. Heap (Priority Queue)

• A binary heap is a complete binary tree used to implement priority queues.
• Used in heap sort algorithm and scheduling algorithms in operating systems.
• Supports efficient retrieval of the minimum or maximum element in O(log n) time.

4. Huffman Coding Tree

• Binary trees are used in data compression algorithms such as Huffman encoding.
• Frequently occurring characters are assigned shorter binary codes and less frequent characters are assigned longer codes.
• Used in file compression tools like ZIP, JPEG, and MP3 encoding.

5. Decision Tree

• Binary trees are used in Artificial Intelligence and Machine Learning to model decisions.
• Each internal node represents a condition/test, and each leaf node represents a decision/outcome.
• Used in game playing algorithms, medical diagnosis systems, and classification problems.

Summary Table

Binary trees form the foundation of many efficient algorithms and data structures used in real-world software systems.

Short Notes

a) Linear Search

Definition: Linear search (also called sequential search) is the simplest searching algorithm that checks each element of a list one by one, from the beginning to the end, until the desired element (key) is found or the list is exhausted.

Algorithm:

LinearSearch(A[], n, key):
1. for i = 0 to n-1 do
2.     if A[i] == key then
3.         return i        // element found at index i
4. return -1               // element not found

Working:

• Start from the first element.
• Compare each element with the search key.
• If a match is found, return the position.
• If the end of the array is reached without a match, return -1 (not found).

Example: Array: [5, 3, 8, 1, 9], Key = 8

• Compare 5 != 8, Compare 3 != 8, Compare 8 == 8 → Found at index 2.

Complexity:

Space Complexity: O(1)

Advantages:

• Simple to implement.
• Works on both sorted and unsorted arrays.
• No preprocessing required.

Disadvantage:

• Inefficient for large datasets compared to binary search.

b) Minimum Spanning Tree (MST)

Definition: A Minimum Spanning Tree of a connected, undirected, weighted graph G = (V, E) is a spanning tree that connects all vertices with the minimum possible total edge weight, containing exactly |V| - 1 edges and no cycles.

Key Properties:

• It spans all vertices (all n vertices are included).
• It is acyclic (no cycles).
• It has exactly n - 1 edges for n vertices.
• The sum of edge weights is minimum among all possible spanning trees.

Example:

Consider a graph with 4 vertices and edges:

A --1-- B
|       |
4       2
|       |
D --3-- C

MST selects edges: A-B (1), B-C (2), C-D (3) → Total weight = 6

Algorithms to Find MST:

Applications:

• Network design (telephone, electrical, road networks).
• Cluster analysis.
• Approximation algorithms for NP-hard problems (e.g., Travelling Salesman Problem).
• Designing least-cost communication networks.

Significance: MST provides the most cost-effective way to connect all nodes in a network, making it fundamental in graph theory and network optimization.