CS301 — Midterm Summary (Lectures 1–22)

📘 Lecture 01 — Data Structures

📖 Overview: This lecture introduces the foundational concepts of data structures, explaining why organizing data is crucial for creating efficient programs. It covers the criteria for selecting appropriate data structures, the philosophy of costs and benefits, and revisits fundamental concepts of arrays and the new List data structure.

🗂️ Topics Covered

This lecture covers the introduction to data structures and their importance for efficient program execution, the process of selecting a data structure based on resource constraints and required operations, the philosophy of weighing costs and benefits for each structure, the goals of the course, a detailed review of arrays (including static and dynamic allocation), and the introduction of the List data structure with its basic operations and the concept of a "current" position marker.

📝 Lecture Summary

Summary

The lecture begins by welcoming students to the data structures course, which is described as a foundational subject. The primary goals are to prepare students for advanced courses, cover well-known data structures like dynamic arrays, linked lists, stacks, queues, trees, and graphs, and implement these structures in C++.

Introduction to Data Structures

Data structures help organize data in the computer, leading to more efficient programs that execute faster and use fewer resources like memory and disk. As computers become more powerful, problems become more complex, but a faster CPU is not always the solution. Efficient programming, using the right data structures and algorithms, is often the key. Organizing data makes it easily accessible for operations like searching or calculating statistics. A solution is efficient if it solves the problem within its resource constraints (time, memory, disk space). Purchasing a faster computer is not always necessary if the software solution is optimized.

Selecting a Data Structure

The selection of a data structure follows a process. First, analyze the problem to determine the resource constraints (e.g., the data is too large for available disk space). Second, determine the basic operations that must be supported (e.g., insert, delete, search) and quantify their resource constraints. Finally, select the data structure that best meets these requirements. For example, inserting an element at the beginning of a filled array requires shifting all existing elements to the right, a costly operation. It is also important to consider if data access is sequential (in a defined order) or random access (no defined order).

🔑 Definition — Resource Constraints: The limitations of a system, such as time, memory, and disk space, which a solution must meet to be considered efficient.

Data Structure Philosophy

Each data structure has associated costs and benefits: space for each data item, time to perform basic operations, and programming effort required. In rare cases, one data structure is better than another in all situations. An important skill is to choose the most appropriate structure for the situation and to program in a way that allows one data structure to be replaced by another without affecting the rest of the program.

Goals of this Course

The course aims to reinforce that every data structure has costs and benefits. Students will learn commonly used data structures, building a programmer's basic data structure "toolkit." A key goal is to understand how to measure the cost of a data structure or program, allowing you to judge the merits of different approaches, such as by comparing performance with small vs. large datasets.

Arrays

An array is a collection of cells of the same type that occupies a contiguous area in computer memory. The array name (e.g., x) is not an lvalue and cannot be used on the left-hand side of an assignment statement. Individual items are accessed using an index (e.g., x[0], x[1]).

int x[6];
for(j = 0; j < 6; j++)
    x[j] = 2 * j;

Dynamic memory allocation is used when the array size is unknown at compile time. The statement int* y = new int[20]; creates an array of 20 integers on the heap, and the pointer y can be used as an lvalue. The memory can be released using delete[] y;.

🔑 Definition — lvalue: A variable that has an associated memory location and can be written on the left-hand side of an assignment statement (e.g., int a; allows a = 5;). 🔑 Definition — Contiguous: Memory locations that are adjacent to each other in the computer's memory.

List data structure

The List data structure is a collection of items of the same type, stored in a particular linear order. It is possible to insert new elements at various positions and remove any element. The list is a set of elements (a1, a2, a3, a4) in a linear order, and this order (e.g., a3, a1, a2, a4) must be maintained.

Key operations on a list include creating a list, copying, clearing, inserting, removing, getting, updating, finding, and returning the length. To specify a "particular position," two approaches are used:

1. Use the actual index of the element (like arrays).
2. Use a "current" marker or pointer to refer to a position in the list.

If using a "current" marker, methods like start(), tail(), next(), and back() are useful for moving the marker.

📌 Example of List Operations:

• createList(): Creates an empty list.
• insert(X, position): Inserts element X at a specific position.
• find(X): Searches for element X in the list.
• length(): Returns the number of elements in the list.

💡 Why this matters: The List data structure is more flexible than an array for many operations (like insertion in the middle) and forms the basis for many other abstract data types like stacks and queues.

⭐ Key Takeaways

The most critical concepts from this lecture are: data structures are essential for organizing data to create efficient programs that respect resource constraints like time and memory. Selecting a data structure requires analyzing the problem, its required operations, and constraints, recognizing that each structure has inherent costs and benefits. Arrays store data of the same type in contiguous memory and allow direct access via index, but are not lvalues themselves; dynamic arrays offer more flexibility with heap-allocated memory. Finally, a List is a new, fundamental data structure representing an ordered collection of elements, which supports operations using either an index or a "current" marker, allowing for more dynamic and flexible data management.

🧠 Quick Revision Questions

1. What are the three main goals of this data structures course?
2. Explain the three steps involved in selecting a data structure to solve a problem.
3. Why is an array name (e.g., x in int x[6]) not considered an lvalue?
4. What is the key difference between accessing elements in a list using an "index" versus a "current marker"?
5. What does it mean for a solution to be "efficient" in the context of resource constraints?

📘 Lecture 02 — Data Structures

📖 Overview: This lecture covers the implementation and analysis of list operations using arrays, including add, remove, find, and other methods. It then introduces the concept of linked memory and linked lists as an alternative to array-based list implementation, addressing the limitations of static memory allocation.

🗂️ Topics Covered

The lecture covers list implementation methods including add, next, remove, and find operations on an array-based list. It provides detailed analysis of each method in terms of time efficiency. The second half introduces linked memory concepts and linked lists, explaining how nodes with data and pointer fields form chains of linked elements.

📝 Lecture Summary

List Implementation

The lecture explains how to implement a list interface using an array internally. For a list of integers (2, 6, 8, 7, 1), the array representation is shown where the current position is 3 and the array index starts from 1 (leaving the zeroth position unused for simplification). The array has two associated variables: current (tracking current position) and size (number of elements in the list).

add Method

The add method inserts a new element at the current position. To add element 9 to the list (2, 6, 8, 7, 1) with current position 3, first every element to the right of position 3 must be shifted one place to the right to create space. Then element 9 is placed at the vacated position. The current pointer moves to the newly inserted element's position, and the size increases by one.

🔑 Definition — add method: Places a new element at the current position by first shifting all elements to the right of that position one step rightward, then inserting the new element.

📌 Example: Adding 9 to list [2, 6, 8, 7, 1] at current position 3:

• Step 1: Shift 7 and 1 right → [2, 6, 8, _, 7, 1]
• Step 2: Insert 9 at position 4 → [2, 6, 8, 9, 7, 1]
• Current becomes 4, size becomes 6

next Method

The next method moves the current pointer one position forward without adding or removing any element. This method is essential for understanding boundary conditions — what happens when we try to move beyond the array's limits. If the array size is 100 and we reach position 100, calling next would cause an error. Similarly, moving backward from the first position creates a boundary condition that requires careful handling in implementation.

remove Method

The remove method removes the element at the current position. When removing element 7 (at position 5) from list [2, 6, 8, 9, 7, 1], the element is removed creating an empty space. All elements to the right of the removed element are shifted one place to the left to fill the gap. The current pointer remains at the same position number, but now points to the element that was shifted left (element 1 in this case). The size decreases by one.

📌 Example: Removing element at position 5 from list [2, 6, 8, 9, 7, 1]:

• Step 1: Remove 7 → [2, 6, 8, 9, _, 1], size = 5 (initially), current = 5
• Step 2: Shift 1 left → [2, 6, 8, 9, 1], current still points to position 5 (now containing 1), size = 5

find Method

The find(x) function searches for a specific element in the list. It traverses the array using a for loop from index 1 to size, comparing each element with x. If the element is found, the function sets current to that position and returns 1 (true). If the element is not found after traversing the entire list, it returns 0 (false).

🔑 Definition — find method: Searches the list for a specified element; if found, sets current to its position and returns true; otherwise returns false.

📌 Code Logic: The for loop runs from j=1 to j < size+1. If A[j] == x, the loop breaks. After the loop, if j < size+1, x was found and current is set to j, returning 1. Otherwise, 0 is returned.

Other Methods

Several simple one-step methods complete the array-based list implementation:

• get() method: Returns the element at the current position — return A[current];
• update(x) method: Sets the value at the current position to x — A[current] = x;
• length() method: Returns the size of the list (number of elements, not array capacity) — return size;
• back() method: Moves the current pointer one element backward — current--;
• start() method: Sets the current position to the first element — current = 1;
• end() method: Sets the current position to the last element — current = size;

Analysis of Array List

The analysis examines the time efficiency of each list operation in terms of CPU time consumption.

Add method analysis: The worst case occurs when adding an element at the beginning of the list, requiring shifting all elements right. If the list has 10,000 or 20,000 elements, all must be shifted using a for loop, consuming significant CPU time. The best case is adding at the end — no shifting required. On average, half the elements must be shifted.

Remove method analysis: The worst case is removing the first element, requiring all remaining elements to shift left. For large lists (10,000-20,000 elements), this is time-consuming. The best case is removing from the end — no shifting needed. On average, half the elements are shifted.

Find method analysis: The worst case requires searching the entire list (element at end or not found). On average, at most half the list is searched.

💡 Why this matters: Understanding these efficiency trade-offs helps programmers choose appropriate implementations and anticipate performance bottlenecks in real applications.

One-step methods: get(), length(), back(), start(), and end() all perform their operations in a single instruction — no loops or complex structures needed.

List using Linked Memory

Array-based lists have limitations: memory cells are contiguous (adjacent in memory), and the array size is fixed at declaration. To increase size, the program must be recompiled or dynamic memory allocation used (with copying of elements to a new array). Linked memory avoids these problems by using memory cells that are not necessarily contiguous. Each cell contains both the element value and information about where the next element is located (its memory address). This creates flexibility in memory usage and dynamic sizing.

Linked List

A linked list is a structure that implements linked memory. It consists of nodes, each containing two fields:

• object field: holds the actual list element
• next field: holds the memory address (pointer) of the next node

🔑 Definition — linked list: A data structure where nodes are connected through pointers, with each node containing data and the address of the next node.

The list (2, 6, 8, 7, 1) is represented as a linked list with nodes chained together. A head pointer points to the first node (essential for accessing the list). A current pointer points to the current node (for add/remove operations). The next field of the last node contains NULL (an invalid, inaccessible address) to mark the end of the list.

In memory, nodes may be scattered at different locations. For example:

• Node containing 2 at memory address 1054, with next field pointing to address 1051
• Node containing 6 at address 1051, with next field pointing to 1063
• Node containing 8 at address 1063, with next field pointing to 1057
• Node containing 7 at address 1057, with next field pointing to 1060
• Node containing 1 at address 1060, with next field pointing to NULL

The head variable holds address 1054 (starting point). The current variable holds address 1063 (current position).

⭐ Key Takeaways

Array-based list operations have varying time efficiencies: add and remove require O(n) shifting in worst case (when operating at the beginning), while find requires O(n) searching in worst case. One-step operations like get, update, length, back, start, and end run in constant O(1) time. Linked lists overcome the limitations of fixed array size and contiguous memory by using nodes with data and pointer fields (containing next node addresses), allowing non-contiguous memory allocation. A head pointer is essential for accessing the linked list, and NULL marks the end of the list. Understanding the trade-offs between array-based and linked-memory implementations is crucial for choosing the right data structure for specific applications.

🧠 Quick Revision Questions

1. What are the steps involved in the add method when inserting an element at the current position in an array-based list?
2. In the remove method, what happens to the current pointer after an element is removed from the list?
3. What are the worst-case, best-case, and average-case time complexities for the add, remove, and find methods in an array-based list?
4. What are the two fields contained in each node of a linked list, and what purpose does each serve?
5. Why is a head pointer necessary in a linked list, and what value is stored in the next field of the last node?

📘 Lecture 3 — Data Structures

📖 Overview: This lecture explores how linked lists are stored in computer memory and how they resolve the fixed-size limitation of arrays. It covers core linked list operations and provides complete C++ implementation code for creating and manipulating linked list nodes.

🗂️ Topics Covered

This lecture examines linked list storage in computer memory, demonstrating how memory chains are formed. It details linked list operations including adding nodes, traversing the list, and managing pointers. The lecture presents complete C++ code for the Node and List classes, with step-by-step explanations of the add() operation with visual diagrams.

📝 Lecture Summary

Linked List inside Computer Memory

A linked list stores elements in nodes scattered throughout memory, each node containing both a data part and a pointer to the next node. The head pointer points to the first node in the list. For example, in a memory snapshot from address 1051 to 1065, the head at address 1062 points to address 1054 containing data element 2. The first node's pointer part contains address 1051 (pointing to the second node). The last node contains 0 in its pointer part, indicating it is the terminal node.

🔑 Definition — Linked List: A linear data structure where each element (node) contains data and a pointer to the next node, allowing dynamic memory allocation.

Linked List Operations

The linked list provides operations to manage nodes. The add() operation creates a new node and inserts it at the current position. The process involves: creating a new node, pointing the new node's next pointer to the node currently after the current position, pointing the current node's next pointer to the new node, and updating the current pointer to the new node.

In C++, creating a new node uses: Node * newNode = new Node(9); — this calls the Node class constructor, passes 9 as parameter, creates the object in memory, and stores its starting address in the pointer variable newNode.

🔑 Definition — new operator: C++ operator that creates objects of classes, calling the constructor function of that class.

📌 Example: Adding node with value 9 to linked list with elements 2, 6, 8, 7, 1 (current pointing to 8):

• Step 1: Point new node's next (9) to node with data 7
• Step 2: Point node with data 8's next to new node (9)
• Step 3: Change current pointer to point to new node (9) Result: Updated list has 6 elements: 2, 6, 8, 9, 7, 1

Linked List Using C++

The Node class contains public methods (get, set, getNext, setNext) and private data members (int object, Node* nextNode). The class acts as a factory that creates node objects. When using the new operator with the Node class, we "order" the Node factory to make nodes for us.

The List class includes a constructor that: creates a new Node for headNode, sets headNode's next to NULL, initializes currentNode to NULL, and sets size to 0. The add() method implements the node insertion logic with two cases: when currentNode exists (list has elements) and when currentNode is NULL (first element being added).

The get() method returns the value of the object pointed to by currentNode, checking that currentNode is not NULL first. The next() method advances currentNode to the next node by storing the current position in lastCurrentNode and updating currentNode using getNext().

🔑 Definition — this pointer: A special pointer in C++ used when an object wants to refer to its own member variables.

🔑 Definition — Inline functions: Functions whose code is replaced by the compiler wherever they are called, used for small functions.

Example Program

The complete source code demonstrates a working linked list implementation with Node and List classes, including friend functions traverse() and addNodes(). The traverse() function walks through the linked list using next() and prints each element, while addNodes() creates a list and adds values 2, 6, 8, 7, and 1.

📌 Example Output:

List size = 5
Element 1 2
Element 2 6
Element 3 8
Element 4 7
Element 5 1

💡 Why this matters: The linked list implementation solves the fixed-size limitation of arrays but requires more complex pointer management and memory overhead for each node's pointer.

⭐ Key Takeaways

The linked list overcomes the array's fixed-size limitation by storing elements as nodes connected through pointers scattered across memory. Each node contains a data part and a next pointer, with the head pointer marking the first node and NULL/0 marking the last node. The add() operation carefully manages pointer assignments to insert new nodes at the current position without shifting elements. The Node and List classes provide encapsulation with public interface methods and private data members. Understanding pointer manipulation is critical for correctly implementing linked list operations.

🧠 Quick Revision Questions

1. What is the significance of the last node's pointer containing 0/NULL in a linked list?
2. What are the three steps required to insert a new node at the current position in a linked list?
3. What does the statement Node * newNode = new Node(9) accomplish in C++?
4. In the List class constructor, why is currentNode initialized to NULL while headNode points to a new Node object?
5. What is the purpose of the lastCurrentNode pointer in the List class, and which method uses it?

📘 Lecture 04 — Data Structures

📖 Overview: This lecture covers the core methods of linked lists, their analysis, and advanced variations including doubly-linked and circularly-linked lists. The Josephus problem provides a practical application demonstrating the utility of circular linked lists for solving real-world elimination problems.

🗂️ Topics Covered

The lecture begins with a detailed explanation of linked list methods including remove, start, and length operations with step-by-step code analysis. It then provides an example of list usage and analyzes the cost-benefit of operations like add, remove, find, and back. The discussion moves to doubly-linked lists with prev pointers for bidirectional traversal, followed by circularly-linked lists that eliminate NULL pointers. The lecture concludes with the Josephus problem as a practical application of circular linked lists.

📝 Lecture Summary

Methods of Linked List

The start() method positions both currentNode and lastCurrentNode at the first element by assigning them the value of headNode. These two pointers point to different nodes, and when calling the next() method, they move forward through the list. In a singly-linked list, pointers cannot move backward past headNode.

The remove() method deletes the node pointed to by currentNode. First, the lastCurrentNode's next pointer is set to bypass the node to be removed: lastCurrentNode->setNext(currentNode->getNext()). This connects the previous node directly to the node after the one being removed.

🔑 Definition — lastCurrentNode: The pointer that points to the node immediately preceding the currentNode in the linked list.

📐 Formula: lastCurrentNode->setNext(currentNode->getNext()) → The previous node's next pointer is updated to point to the node after the current node, effectively removing the current node from the chain.

📌 Example: In a list with values 2 → 6 → 8, with currentNode pointing to 6 and lastCurrentNode pointing to 2, after calling setNext, the next pointer of node 2 points directly to node 8, disconnecting node 6.

The second step uses delete currentNode to free the memory allocated with the new keyword. The third step moves currentNode to lastCurrentNode, and the fourth step decrements the list size with size--.

The length() method simply returns the private data member size. The private data members of the list class include size (list size), headNode (pointer to first node), currentNode, and lastCurrentNode.

💡 Why this matters: Understanding pointer manipulation in remove operations is critical because incorrect ordering can break the linked chain and cause memory leaks or segmentation faults.

Example of list usage

A program demonstrates linked list usage by creating a List object, adding values (5, 13, 4, 8, 24, 48, 12), calling the start() method to position pointers at the beginning, then using a while loop with next() and get() methods to traverse and display all elements.

The next() method returns a boolean value — true if movement was successful, false when reaching the end of the list. The get() method retrieves the value of the current node. The output shows all seven elements in order of insertion.

💡 Why this matters: This demonstrates the interface-based programming approach where users interact with methods without worrying about internal implementation details (whether array, linked list, or other structure).

Analysis of Link List

The add operation is a one-step operation — inserting a new node after the current node requires changing two or three pointers without traversing the list. Compared to arrays, which require shifting all subsequent elements rightward, linked list insertion is more efficient.

The remove operation is also a one-step operation — connecting the node before and after the target node, updating the current pointer, and deleting the node. For arrays, deletion requires shifting all later elements one position left.

The find operation in the worst case requires searching the entire list from start to end. The average case requires searching half the list. This is identical to array searching since no ordering exists.

The back operation is not a one-step operation in singly-linked lists. Moving the current pointer backward requires traversing from the start of the list until reaching the node whose next pointer contains the address of the current node. If currentNode and lastCurrentNode are at the end, the entire list must be traversed.

💡 Why this matters: The back operation's inefficiency demonstrates the fundamental limitation of singly-linked lists and motivates the development of doubly-linked lists.

Doubly-linked List

A doubly-linked list node contains three parts: prev (pointer to previous node), element (data), and next (pointer to next node). The prev pointer enables bidirectional traversal.

The Node class includes getPrev() and setPrev() methods in addition to the standard get/set methods. The getPrev method returns a Node* pointer to the previous node, while setPrev assigns an address to the prev pointer.

To insert a new node (value 9) between nodes with values 6 and 8 in a doubly-linked list:

1. Set newNode's next to point to the node after current: newNode->setNext(current->getNext())
2. Set newNode's prev to point to current: newNode->setPrev(current)
3. Set the node after current's prev to point to newNode: (current->getNext())->setPrev(newNode)
4. Set current's next to newNode: current->setNext(newNode)
5. Update current to newNode and increment size

📐 Formula for doubly-linked insert ordering: Next of new node → node after current, Prev of new node → current, Prev of node after current → new node, Next of current → new node.

💡 Why this matters: The order of pointer reorganization in doubly-linked lists is critical — incorrect ordering can break both forward and backward links, making the list unusable.

Circularly-linked lists

A circularly-linked list connects the last node's next pointer to the first node, eliminating NULL pointers. In singly-linked circular lists, the next method never returns NULL. In doubly-linked circular lists, the first node's prev points to the last node, and the last node's next points to the first node.

The benefit is that next() and back() methods never encounter NULL pointers, preventing potential errors from accessing NULL pointers. The head pointer remains at its position unless the node it points to is removed.

📌 Example: A circular singly-linked list with values 2, 6, 8, 7, 1 has the last node (1) pointing back to the first node (2), forming a continuous circle without any NULL next pointer.

💡 Why this matters: Circular linked lists are essential for applications requiring continuous traversal, such as round-robin scheduling, game loops, and the Josephus problem.

Josephus Problem

The Josephus Problem involves N persons sitting in a circle, counting M persons, and eliminating the M-th person until only one remains. The circular linked list is the optimal data structure for this problem.

With N=10 and M=3, persons are numbered 1-10 in a circle. Starting from person 1, counting 3 reaches person 4 (eliminated). Counting from person 5, person 8 is eliminated. This continues until only person 5 remains as the leader.

The program uses a CList (circularly-linked list) factory to create the list, adds numbers 1 to N, points pointers to the start, then repeatedly calls next() M times and remove() until only one node remains. The surviving node's value is displayed as the leader.

🔑 Definition — Josephus Problem: A theoretical problem where N individuals stand in a circle and every M-th person is eliminated until only one remains, used to demonstrate circular linked list applications.

📌 Example: With N=10, M=3: Elimination order is 4, 8, 2, 7, 3, 10, 9, 1, 6, and leader is person 5. The while loop continues as long as list.length() > 1, with each iteration counting M steps and removing the current node.

💡 Why this matters: The Josephus problem demonstrates how choosing the right data structure (circular linked list) simplifies implementation. Variations where M changes each round show the flexibility of this approach over mathematical formulas.

⭐ Key Takeaways

Linked list remove is a one-step pointer adjustment operation, unlike arrays which require shifting all later elements. The back operation in singly-linked lists is inefficient, requiring traversal from the start — this limitation is overcome by doubly-linked lists which store prev pointers for bidirectional movement. Doubly-linked list insertion requires careful ordering of four pointer updates to maintain both forward and backward links. Circularly-linked lists eliminate NULL pointers by connecting the last node to the first, making traversal safe from NULL pointer exceptions. The Josephus problem demonstrates that circular linked lists are the optimal structure for elimination problems involving circular counting.

🧠 Quick Revision Questions

1. What are the four steps of the remove() method in a singly-linked list, and what does each step accomplish?
2. Why is the back() operation inefficient in a singly-linked list, and how does a doubly-linked list solve this problem?
3. What is the correct order of pointer updates when inserting a new node into a doubly-linked list?
4. How does a circularly-linked list differ from a regular linked list in terms of NULL pointers?
5. In the Josephus problem, why is a circular linked list the optimal data structure rather than a regular linked list?

📘 Lecture 05 — Data Structures

📖 Overview: This lecture covers the benefits of using circular linked lists, introduces the concept of Abstract Data Types (ADT), and begins the study of stacks—a fundamental LIFO data structure. The lecture culminates in a detailed implementation of a stack using arrays in C++, demonstrating how encapsulation and ADTs simplify complex problem-solving.

🗂️ Topics Covered

The lecture revisits the Josephus problem solution using the CList class to demonstrate code reusability and encapsulation. It then discusses the benefits of circular linked lists over arrays for such problems. The concept of Abstract Data Type (ADT) is introduced, emphasizing the separation of interface from implementation. Finally, stacks are defined as a LIFO structure, with their core operations (push, pop, top) explained and implemented using an array in C++.

📝 Lecture Summary

Benefits of using circular list

Using the CList class to solve the Josephus problem made the solution trivial. The program simply included the class and called its methods (add, start, length, next, get, remove). The programmer does not need to worry about how the list is implemented (e.g., singly linked, doubly linked, or array). This encapsulation and reusability of code are major benefits. In contrast, solving the same problem with an array in the main program would require complex manual code for moving through elements and removing them, making the code difficult to understand, modify, and reuse. The choice of an appropriate data structure simplifies the algorithm and makes it more efficient.

🔑 Definition — Encapsulation: Bundling data (attributes) and methods (functions) that operate on that data within a single unit (a class), hiding the internal implementation details from the user. 💡 Why this matters: A properly constructed data structure, like the circular list, helps solve problems efficiently, while a poor choice makes code complex.

Abstract Data Type

A data type is a collection of values and a set of operations on those values. An Abstract Data Type (ADT) refers to the basic mathematical concept that defines the data type, independent of its implementation. In the course, four different implementations of the list data structure were discussed (array, singly linked list, doubly linked list, circular linked list). The program using the list is not concerned with its internal implementation; the interface (methods like add, get, next) remains the same. This encapsulation means the implementation can be changed without affecting the user of the ADT. C++ classes provide a way to create such ADTs. While users are independent of internal workings, they must still ensure the ADT is efficient (not a bottleneck). The source code of ADTs is often provided in compiled (binary) form, with only the interface (.h file) visible.

🔑 Definition — Abstract Data Type (ADT): A mathematical model for a data type that defines the data and the operations on that data, but hides the details of how those operations are implemented.

Stacks

A stack is a collection of elements arranged in a linear order where all insertions and removals occur at one end, called the top. The real-life example is a stack of plates. The core interface methods for a stack are:

• push(x): Insert x as the top element of the stack.
• pop(): Remove the top element of the stack and return it.
• top(): Return the top element without removing it from the stack.

Because the last element pushed is the first one to be popped, a stack is known as a LIFO (Last In, First Out) structure. To handle edge cases like popping from an empty stack, a boolean method isEmpty() is typically provided. The user is responsible for calling isEmpty() before pop() to avoid errors.

📌 Example:

1. push(2), push(5), push(7), push(1) → Stack (top to bottom): [1, 7, 5, 2]
2. pop() → Returns 1. Stack: [7, 5, 2]
3. push(21) → Stack: [21, 7, 5, 2]
4. pop() → Returns 21. Stack: [7, 5, 2]
5. pop() → Returns 7. Stack: [5, 2]
6. pop() → Returns 5. Stack: [2]

Stack Implementation using array

Stacks can be implemented using arrays. To avoid inefficient shifting of elements, the push() and pop() operations should be implemented at the end of the array (not the beginning). The array is indexed, and a variable top (often current) holds the index of the most recent element. Since arrays have a fixed maximum size, an isFull() method is also provided to check if the array is full before pushing.

The C++ code for the stack class using an array of size 10 is:

class Stack {
public:
    Stack() { size = 10; current = -1; }
    int pop() { return A[current--]; }
    void push(int x) { A[++current] = x; }
    int top() { return A[current]; }
    int isEmpty() { return ( current == -1 ); }
    int isFull() { return ( current == size-1 ); }
private:
    int current; // Index of the array
    int size;    // max size of the array
    int A[10];   // Array of 10 elements
};

In the main() function, a user creates a Stack object and calls push() and pop() after checking isFull() and isEmpty() respectively. A quick examination shows that all five operations (push, pop, top, isEmpty, isFull) take constant time, meaning their execution time does not depend on the number of elements in the stack.

📐 Formula: Stack methods are O(1) (constant time complexity) for all operations. 📌 Example: Running the provided main() code which attempts to push 12 elements into a stack of size 10 produces output showing that after the 10th element, a "Stack is full" message appears. Similarly, after popping all 10 elements, a "Stack is empty" message appears for further pop attempts.

⭐ Key Takeaways

The Circular Linked List (via the CList class) dramatically simplifies the Josephus problem by providing a ready-made interface for manipulation, demonstrating code reusability. The Abstract Data Type (ADT) concept is crucial: it separates the interface (the what) from the implementation (the how), allowing the implementation to change without affecting the user. Stacks are a LIFO (Last In, First Out) data structure where all operations (push, pop, top) happen at one end (the top). In an array-based implementation, push and pop should be done at the end of the array to achieve O(1) constant time complexity for all stack operations. The user is responsible for managing stack boundaries by calling isEmpty() and isFull() before pop() and push().

🧠 Quick Revision Questions

1. What is an Abstract Data Type (ADT) and why is it beneficial in programming?
2. List the three core operations of a Stack data structure and describe what each does.
3. Explain why a Stack is called a LIFO structure. Provide a real-world analogy.
4. In an array-based implementation of a Stack, why is it more efficient to push and pop elements at the end of the array rather than the beginning?
5. What are the isEmpty() and isFull() methods used for, and who is responsible for calling them?

📘 Lecture 06 — Data Structures

📖 Overview: This lecture explores the implementation of the stack data structure using a linked list, contrasting it with array-based implementation. It also introduces the concept of expression notation (infix, prefix, postfix) and operator precedence, laying the groundwork for using stacks in expression evaluation and conversion.

🗂️ Topics Covered

The lecture begins with a recap of stack implementation using arrays and its limitations, then introduces linked list-based stack implementation with code for push(), pop(), top(), and isEmpty() operations. It compares array vs. linked list stack implementations, discusses the use of stacks in expression evaluation, covers infix, prefix, and postfix notation, explains operator precedence rules, and provides examples of infix to postfix conversion.

📝 Lecture Summary

Stack From the Previous Lecture

In the previous lecture, we implemented a stack using an array with push(), pop(), and top() operations. The isFull() method was necessary because arrays have fixed size, and pushing elements without checking could crash the program. The isEmpty() method is inherent to stack functionality, regardless of implementation. The fixed-size limitation of arrays motivates using linked lists for stack implementation.

Stack Using Linked List

Using a linked list avoids the size limitation of array-based stacks. For LIFO (Last In, First Out) behavior, we must decide where to insert and delete elements for optimal efficiency. With a singly-linked list, insertion and removal at the start both take constant time, while removal at the end requires traversal. Therefore, we implement push() by inserting at the start and pop() by removing from the start.

🔑 Definition — LIFO (Last In, First Out): The stack property where the most recently added element is the first one to be removed.

The pop() operation:

• Retrieves the value from the node pointed by head
• Saves the head pointer in a temporary pointer
• Moves head to point to the next node
• Deletes the old node
• Returns the retrieved value

The push(x) operation:

• Creates a new Node object
• Sets the value x into the new node
• Links the new node to the current head (setNext(head))
• Updates head to point to the new node

The top() operation simply returns the value at head without removing it. The isEmpty() operation checks if head is NULL.

All four operations (push, pop, top, isEmpty) take constant time — they contain no loops. The isFull() method is not needed with linked list implementation because memory allocation is dynamic, though the stack is ultimately limited by the computer's address space (2³²-1 for 32-bit or 2⁶⁴-1 for 64-bit systems).

Stack Implementation: Array or Linked List

Both implementations support stack operations in constant time, but each has trade-offs:

• Time overhead: Allocating and de-allocating list nodes at runtime takes more time than using a pre-allocated array.
• Memory efficiency: Linked lists consume only as much memory as needed by actual nodes, while arrays allocate a fixed chunk upfront (e.g., allocating 1000 slots but using only 50 wastes 950 slots).
• Extra memory for pointers: Each node in a singly-linked list requires an extra next pointer (4 or 8 bytes per node), adding overhead.
• Upper limit: Arrays have a fixed upper limit; linked lists are limited only by the machine's address space.

💡 Why this matters: The choice between array and linked list for stack implementation depends on whether priority is time efficiency (array) or memory flexibility (linked list).

Use of Stack

Stacks are used for traversing and evaluating prefix, infix, and postfix expressions.

In an infix expression like A+B, the operator is between the operands (e.g., A + B). In a prefix expression, the operator comes before operands (e.g., +AB). In a postfix expression, the operator comes after operands (e.g., AB+).

For the expression A + B * C, multiplication has higher precedence, so it is interpreted as A + (B * C). Converting to postfix:

1. Convert multiplication: A + (B C *)
2. Convert addition: A (B C *) +
3. Result: A B C * +

For (A + B) * C:

1. Convert addition: (A B +) C *
2. Result: A B + C *

Precedence of Operators

The five binary operators have the following precedence (highest to lowest):

• Exponentiation (^)
• Multiplication/division (*, /)
• Addition/subtraction (+, -)

For operators of same precedence, the left-to-right rule applies: A+B+C means (A+B)+C. For exponentiation, the right-to-left rule applies: A ^ B ^ C means A ^ (B ^ C).

Examples of Infix to Postfix

⭐ Key Takeaways

Linked list implementation of a stack eliminates the fixed-size limitation of arrays and removes the need for isFull(), though it introduces overhead from dynamic memory allocation and extra pointer storage per node. All stack operations (push, pop, top, isEmpty) execute in constant time regardless of implementation. Infix expressions place operators between operands, while postfix places operators after operands, and prefix places operators before operands. Operator precedence rules govern the order of evaluation: exponentiation first, then multiplication/division, then addition/subtraction. Understanding infix-to-postfix conversion is essential for evaluating expressions using stacks.

🧠 Quick Revision Questions

1. Why does linked list implementation of a stack use insertion and removal at the start rather than the end?
2. What are the trade-offs between array-based and linked list-based stack implementations?
3. Why is isFull() not needed in linked list stack implementation but isEmpty() is still required?
4. Convert the infix expression (A - B) / C to postfix form.
5. What is the rule for evaluating operators with the same precedence in an expression?

📘 Lecture 07 — Data Structures

📖 Overview: This lecture focuses on evaluating postfix expressions using a stack and converting infix expressions to postfix form. It introduces the stack-based algorithm for postfix evaluation and the conversion process using operator precedence and a stack data structure.

🗂️ Topics Covered

The lecture covers three main topics: evaluation of postfix expressions using a stack with a detailed algorithm and example, a comprehensive worked example of evaluating a long postfix expression step-by-step in tabular form, and infix to postfix conversion including the algorithm, operator precedence handling, and the role of parentheses.

📝 Lecture Summary

Evaluating postfix expressions

Postfix notation places operators after their operands and does not use parentheses. To evaluate a postfix expression, we use a stack. We read the expression from left to right. When we encounter an operand, we push it onto the stack. When we encounter an operator, we pop the top two operands from the stack (op2 first, then op1), apply the operator, and push the result back onto the stack. At the end, the stack will contain the final result.

🔑 Definition — Postfix Expression: A mathematical expression where operators follow their operands (e.g., A B + instead of A + B). No parentheses are needed.

📐 Algorithm:

Stack s;
while( not end of input ) {
    e = get next element of input
    if( e is an operand )
        s.push( e );
    else {
        op2 = s.pop();
        op1 = s.pop();
        value = result of applying operator 'e' to op1 and op2;
        s.push( value );
    }
}
finalresult = s.pop();

📌 Example: Evaluate postfix expression 432*+

• Push 4, 3, 2 onto stack (top to bottom: 2, 3, 4)
• Read *: pop op2=2, op1=3 → 3*2=6 → push 6 (stack: 6, 4)
• Read +: pop op2=6, op1=4 → 4+6=10 → push 10
• Final result: 10

💡 Why this matters: Stack-based evaluation is efficient because it eliminates the need for parentheses and precedence rules during evaluation.

An Example

We evaluate the long postfix expression 6 2 3 + - 3 8 2 / + * 2  3 + step-by-step:

Final result: 52

🔑 Definition — Stack LIFO behavior: The last element pushed is the first popped, which is why op2 is popped first and op1 second when evaluating operators.

📌 Key rules: Always pop op2 first (top of stack), then op1. Apply operator as op1 op op2.

Infix to postfix Conversion

To convert an infix expression (with operators between operands like A+B) to postfix form, we use a stack for operators. The order of operands remains unchanged, but operators may be reordered based on precedence. We use a function prcd(op1, op2) that returns TRUE if op1 has precedence over op2.

🔑 Definition — prcd function: A function that determines operator precedence. prcd(*, +) returns TRUE; prcd(+, *) returns FALSE.

📐 Algorithm:

Stack s;
while( not end of input ) {
    c = next input character;
    if( c is an operand )
        add c to postfix string;
    else {
        while( !s.empty() && prcd(s.top(),c) ) {
            op = s.pop();
            add op to the postfix string;
        }
        s.push( c );
    }
}
while( !s.empty() ) {
    op = s.pop();
    add op to postfix string;
}

📌 Example: Convert infix A+B*C to postfix

For parentheses in infix expressions:

• When ( is read, push it on the stack (prcd(op, '(') = FALSE)
• When ) is read, pop all operators up to the first ( and place them in postfix string
• Both parentheses are discarded (not added to postfix string)

🔑 Definition — Parenthesis handling in conversion: The open parenthesis is pushed as a marker; when closing parenthesis is encountered, all operators up to the open parenthesis are popped and added to postfix.

📌 Special prcd rules for parentheses:

• prcd('(', op) = FALSE for any operator
• prcd(op, ')') = FALSE for any operator other than ')'
• prcd(op, ')') = TRUE for any operator other than '('

⭐ Key Takeaways

Students must remember that stack is used both for evaluating postfix expressions and converting infix to postfix. For postfix evaluation, always push operands, and when encountering an operator, pop op2 first (top) then op1, apply the operator as op1 op op2, and push the result. For infix to postfix conversion, send operands directly to output, push operators on stack but before pushing, pop all operators with higher precedence from the stack to output. Parentheses require special handling — open parenthesis is pushed onto stack and acts as a lower precedence barrier, while closing parenthesis pops all operators until the matching open parenthesis, and both are discarded.

🧠 Quick Revision Questions

1. What are the steps to evaluate the postfix expression 5 3 + 2 * using a stack?
2. In postfix evaluation, why is op2 popped before op1, and what would happen if the order were reversed?
3. Convert the infix expression (A+B)*C-D to postfix form using the algorithm.
4. When processing the infix expression A+B*C, why is + not added to postfix immediately after A?
5. How does the algorithm handle a closing parenthesis ) during infix to postfix conversion, and why are parentheses not included in the final postfix expression?

📘 Lecture 08 — Data Structures (CS301)

📖 Overview: This lecture focuses on the conversion of infix expressions with parentheses to postfix notation, details the evaluation process using a stack, and introduces the powerful C++ template mechanism for creating generic data structures. It also explores the fundamental role of the stack as the function call stack in program execution and memory management.

🗂️ Topics Covered

The lecture covers the conversion algorithm for infix to postfix expressions including parentheses handling, with a detailed step-by-step example. It then introduces C++ templates as a solution for writing generic code for data structures like Stack, providing a complete template class implementation and its usage. Finally, it explains the function call stack mechanism, including parameter passing, return addresses, and the runtime memory organization of a process.

📝 Lecture Summary

Conversion from infix to postfix

In the previous lecture, we discussed the way to convert an infix notation into a postfix notation. During the process of conversion, we saw that there may be a need for parentheses in the infix, especially when we want to give a higher precedence to an operator of lower precedence. For example, to force addition before multiplication in A + B * C, we write (A + B) * C. We have defined the return values for opening ( and closing ) parentheses in the precedence function.

The process of converting the infix expression (A + B) * C into a postfix expression is completed in eight steps, as shown in the following table. The symbol column has the input symbols, the postfix column has the postfix string after each step, and the stack is used to store operators.

First, the opening parenthesis ( is put on the stack. The next symbol A is an operand, so it goes to the postfix string. The + operator is pushed onto the stack. Then operand B is placed in the postfix string. When the closing parenthesis ) appears, the operators (in this case +) are popped from the stack and put in the postfix string, and the opening parenthesis is also popped and discarded. The next operator * is pushed onto the stack. After operand C is placed in the postfix string, the input string ends. The remaining * operator is popped from the stack and put into the postfix string, yielding AB+C*.

🔑 Definition — Conversion algorithm: A process that uses a stack to rearrange operators according to precedence and parentheses, producing a postfix expression where operators appear after their operands and parentheses are removed.

Now, we apply the evaluation algorithm on this postfix expression AB+C*. The two operands A and B go to the stack. The operator + pops these operands, adds them, and pushes the result back onto the stack. Next C goes to the stack, and then * operator pops the two operands (result of addition and C), and their multiplication leads to the final result. The postfix notation is simple to evaluate because operators are in the order of evaluation, unlike infix which requires parentheses to force precedence. With the help of a stack data structure, we can do the conversion and evaluation of expressions easily.

💡 Why this matters: Understanding this conversion is crucial because computers evaluate postfix expressions much more efficiently than infix expressions, making this a fundamental algorithm for compilers and calculators.

C++ Templates

We can use C++ templates for stack and other data structures. When converting expressions, we use the stack for storing operators like +, *, -, and /, which are single characters. When evaluating expressions, we store operands (integers, floats, or variables). In both cases, the functionality is the same – we push and pop things, and check if the stack is empty. The only difference is the type of elements used.

Without templates, we would have to create separate classes like FloatStack and CharStack with identical code, just differing in data type. C++ provides templates to write the code for a stack once and then use it for different types of data. A template is a function or class written with a generic data type. When a programmer uses this function or class, the generic data type is replaced with the specific data type needed.

The lecture presents a template class for stack declared in the file Stack.h:

template <class T>
class Stack
{
public:
    Stack();
    int empty(void);
    int push(T &);
    T pop(void);
    T peek(void);
    ~Stack();
private:
    int top;
    T* nodes;
};

The line template <class T> shows we are writing a template. Here T is a variable name for a generic data type. A data type will replace this T whenever the template is used. The peek function is similar to the top function – it returns the element from the top but does not remove it from the stack.

The implementation in Stack.cpp includes:

template <class T>
Stack<T>::Stack()
{
    top = -1;
    nodes = new T[MAXSTACKSIZE];
}

template <class T>
int Stack<T>::push(T& x)
{
    if( top < MAXSTACKSIZE )
    {
        nodes[++top] = x;
        return 1;
    }
    cout << "stack overflow in push.\n";
    return 0;
}

template <class T>
T Stack<T>::pop(void)
{
    T x;
    if( !empty() )
    {
        x = nodes[top--];
        return x;
    }
    cout << "stack underflow in pop.\n";
    return x;
}

The main program in main.cpp demonstrates the usage:

Stack<int> intstack;
Stack<char> charstack;
int x=10, y=20;
char c='C', d='D';

intstack.push(x);  intstack.push(y);
cout << "intstack: " << intstack.pop() << ", " << intstack.pop() << "\n";
charstack.push(c); charstack.push(d);
cout << "charstack: " << charstack.pop() << ", " << charstack.pop() << "\n";

The line Stack<int> intstack creates an object where the generic data type T is replaced by int, making it a stack for integers. Similarly, Stack<char> charstack creates a stack for characters. The compiler automatically provides two versions of the template code. This is possible only in C++ through the template utility. C++ also provides the Standard Template Library (STL), which is a tested code base containing common data structures like stack and queue as templates.

💡 Why this matters: Templates enable code reuse and type safety without duplication, allowing us to define a data structure once and use it with any data type.

Function Call Stack

Whenever a programmer calls a function, they pass some arguments to the function, which does work on these arguments and returns a value. The function call stack is used by the compiler to fulfill this function call. The compiler puts entries on the stack in the following way: first (on the top) is the return address where control will go back after executing the function. After it, the next entries are the arguments of the function. The compiler pushes the last argument first (so it goes to the bottom), then the second last, and so on, making the first argument the first element on the stack.

top ------ >   return address
               first argument
               second argument
               .........
               .........
               last argument

Consider the function:

int i_avg (int a, int b)
{
    return (a + b) / 2;
}

The assembly language code shows the use of the stack pointer %esp:

_i_avg:
movl 4(%esp), %eax     # Gets first argument (offset 4 from top)
addl 8(%esp), %eax     # Adds second argument (offset 8 from top)
sarl $1, %eax          # Divide by 2
ret                    # Return value is in %eax

The esp register is the stack pointer (top). The movl takes offset 4 from top (4 bytes for an integer) to get the first argument. The addl takes offset 8 from the stack pointer for the second argument. The sarl divides by 2, and ret returns the value.

Different data structures are used in the run time environment of the computer. When an executable program runs, it is loaded in memory and becomes a process. This process is given a block of memory which it uses during its execution. The internal memory organization of a process includes:

• Code: The code generated by the compiler
• Static data: Holds global variables and different variables of objects
• Stack: Used in function calls
• Heap: Used for dynamic memory allocation

The task manager shows details of all running programs, including their Process ID (PID) and memory usage (Mem Usage). The whole process of using the stack in function calling is known as the run time environment.

💡 Why this matters: Understanding the function call stack is fundamental for debugging, understanding recursion, and ultimately for writing compilers or understanding low-level program execution.

⭐ Key Takeaways

This lecture provides the complete implementation of a generic stack using C++ templates, demonstrating how to write a single code base that works for any data type. The key skill is understanding the infix-to-postfix conversion algorithm with parentheses, which is essential for expression evaluation in compilers and calculators. The function call stack mechanism reveals how the computer actually passes arguments and returns control during function execution. Finally, the runtime memory organization (code, static data, stack, heap) is crucial for understanding program execution, memory management, and debugging.

🧠 Quick Revision Questions

1. In the conversion of (A + B) * C to postfix, what happens when the closing parenthesis ) is encountered?
2. What is the purpose of the template <class T> declaration in a C++ template class?
3. In the function call stack, what is stored at the top of the stack when a function is called?
4. What are the four main sections of a process's memory organization, and which one is used for dynamic memory allocation?
5. Why can't you push a character value onto a stack created as Stack<int>?

📘 Lecture 09 — Data Structures

📖 Overview: This lecture explores memory organization in processes, including stack layout during function calls, and introduces the queue data structure. It covers queue implementation using both linked lists and arrays (including circular arrays), along with practical applications like simulation.

🗂️ Topics Covered

Memory organization in processes (code section, static data, stack, heap), stack layout during function calls, introduction to queues as FIFO data structures, queue operations (enqueue, dequeue, front, isEmpty), implementing queue using linked list with front and rear pointers, implementing queue using circular arrays with modulo arithmetic, and practical applications of queues in simulation.

📝 Lecture Summary

Memory Organization

When you run an executable, the operating system creates a process inside memory and constructs four main sections. A code section contains the binary version of the program's code. A section for static data includes global variables. The stack is used for function calling, while the heap area is utilized during dynamic memory allocation.

Stack Layout during a Function Call

The diagrams depict the layout of the stack when a function F calls function G. Here sp stands for stack pointer. Before function F calls function G, the parameters passed to function F are first inserted into the stack, followed by local variables of function F, and finally the memory address to return after function F finishes. Just before G is called, parameters being passed to G are inserted into the stack.

After the call to function G, local variables of function G are inserted into the stack after its parameters and return address. When function G finishes execution, its local variables and parameters are removed permanently from the stack. Thus, when a function call is made, all local variables and parameters of the called function are pushed onto the stack and destroyed soon after execution completes.

In C/C++, variables declared as static are not pushed on the stack. Rather, these are stored in a separate section allocated for static data of a program. This section is not destroyed till the end of the process's execution. If a variable x is declared as static inside function G, x will be stored in the static data section and its value is preserved across G function calls. The visibility of x is restricted to function G only.

💡 Why this matters: Understanding stack layout is crucial for debugging, understanding recursion, and managing memory efficiently in programs.

Queues

A queue is a linear data structure into which items can only be inserted at one end and removed from the other. In contrast to the stack, which is a LIFO (Last In First Out) structure, a queue is a FIFO (First In First Out) structure. The usage of queue in daily life is common - we queue up while depositing a bill or purchasing a ticket, where the first person is served first.

Queue Operations

The queue data structure supports the following operations:

🔑 Definition — enqueue(X): Place X at the rear of the queue 🔑 Definition — dequeue(): Remove the front element and return it 🔑 Definition — front(): Return front element without removing it 🔑 Definition — isEmpty(): Return TRUE if queue is empty, FALSE otherwise

Implementing Queue

Suppose we are implementing queue with the help of the linked list structure. Key points include: Insert works in constant time for either end of a linked list; Remove works in constant time only; Best that head of the linked list be the front of the queue so all removes will be from the front; Inserts will be at the end of the list.

The queue elements are shown with two pointers: front and rear. When dequeue() is called once, the front element is removed and the front pointer moves to the next element. When enqueue(9) is called, the new element is inserted at the rear end and the rear pointer points to this new node.

dequeue() code:

int dequeue() {
    int x = front->get();
    Node* p = front;
    front = front->getNext();
    delete p;
    return x;
}

enqueue(int x) code:

void enqueue(int x) {
    Node* newNode = new Node();
    newNode->set(x);
    newNode->setNext(NULL);
    rear->setNext(newNode);
    rear = newNode;
}

In dequeue(), the front element is retrieved and assigned to x. The front pointer is saved in p, then moved forward. The node pointed to by front is deleted, and the saved value is returned.

In enqueue(), a new Node object is created using new Node(). The value x is set in the new node, its next pointer is set to NULL. The new node is set as the next node of the node pointed by rear, and rear is updated to point to the new node.

front() and isEmpty() code:

int front() {
    return front->get();
}

int isEmpty() {
    return (front == NULL);
}

The front() method retrieves the oldest element inserted in the queue. The isEmpty() method checks if the front pointer is NULL, returning true if the queue is empty.

Queue using Array

Before implementing a queue with an array, consider: If we use an array to hold queue elements, both insertions and removal at the front (start) of the array are expensive due to shifting up to "n" elements. For a queue, both ends are required. To get around this, we will not shift upon removal of elements.

In array implementation, front and rear are not pointers but indexes of arrays. front contains the starting index (0) while rear comprises the last element's index. When an element is removed from the queue, we do not shift the array elements, as shifting might be expensive.

However, after insertions and removals, we create a new problem - we cannot insert new elements even though there are empty places at the start of the array.

🔑 Definition — Circular Array: The solution lies in allowing the queue to wrap around by using a circular array to implement the queue.

The number of locations in the circular array are eight, starting from index 0 to 7, incremented in the clockwise direction. To insert an element, we insert it in the location next to the last used index.

enqueue() for circular array:

void enqueue(int x) {
    rear = (rear + 1) % size;
    array[rear] = x;
    noElements = noElements + 1;
}

In line 1, 1 is added to rear and the mod operator (%) is applied with size variable. This expression can result from 0 to 7 as size is 8. This operator ensures the value will always be within range.

We also need to maintain four variables: front, rear, size, and noElements.

isFull() and isEmpty() methods:

int isFull() {
    return noElements == size;
}

int isEmpty() {
    return noElements == 0;
}

isFull() returns true if the number of elements equals the size of the array. isEmpty() returns true if noElements equals 0.

dequeue() for circular array:

int dequeue() {
    int x = array[front];
    front = (front + 1) % size;
    noElements = noElements - 1;
    return x;
}

In the first line, we take out an element from the array at front index and store it in x. In the second line, front is incremented by 1 but using modulo for circular behavior. In the third line, number of elements is reduced by 1 and the saved element is returned.

Use of Queues

Out of the numerous uses of queues, one of the most useful is simulation. A simulation program attempts to model a real-world phenomenon. Many popular video games are simulations, e.g., SimCity, Flight Simulator. Each object and action in the simulation has a counterpart in the real world.

Example: Suppose there is a bank with four tellers. A customer enters at time t₁ desiring to conduct a transaction. Any teller can attend to the customer. The transaction will take time t₂. If a teller is free, the customer leaves at t₁+t₂. If no teller is free, the customer goes to the shortest line and waits. The customer leaves at t₂ time units after reaching the front of the line. The time spent at the bank is t₂ plus time waiting in line.

⭐ Key Takeaways

The lecture covers two major topics: memory organization with stack layout during function calls, and the queue data structure. Understanding how the stack stores parameters, local variables, and return addresses during function calls is essential. Queues operate on FIFO principle, with enqueue at rear and dequeue from front. Queue can be implemented using linked lists (constant time operations) or circular arrays (using modulo arithmetic to wrap around). The circular array approach solves the problem of wasted space in regular array implementation. Queues are widely used in simulation applications for modeling real-world scenarios.

🧠 Quick Revision Questions

1. What four sections does the operating system create in memory when running an executable?
2. What happens to static variables during function calls compared to local variables?
3. What is the difference between stack (LIFO) and queue (FIFO) data structures?
4. How does the modulo operator help in implementing a circular array for queues?
5. In the bank simulation example, what determines the total time a customer spends at the bank?

📘 Lecture 10 — Queues, Simulation Models, Priority Queue & Code of the Bank Simulation

📖 Overview: This lecture extends the queue data structure by applying it to real-world simulation problems, specifically a bank teller simulation. It introduces two simulation models—time-based and event-based—and explains the priority queue data structure, which is essential for handling events in order of their occurrence rather than arrival order.

🗂️ Topics Covered

The lecture covers queue applications in bank simulation scenarios, two simulation models (time-based and event-based), the concept of priority queues as a generalization of FIFO queues, and the complete C++ code implementation of a bank simulation. The lecture also demonstrates how to calculate key performance metrics such as average customer wait time using simulation.

📝 Lecture Summary

Queues

The lecture begins by revisiting the queue data structure and demonstrating its usefulness in simulation, specifically a bank scenario. Customers enter a bank with four tellers and form queues. A person enters, analyzes the four queues, and joins the shortest one. The person cannot change queues once selected. The simulation tracks when customers arrive, how long they wait, and when they leave.

🔑 Definition — Queue (from prior lecture): A FIFO (First In, First Out) data structure where elements are added at the rear and removed from the front.

📌 Example: A customer arrives at 10:00 AM with a 5-minute transaction time, waits 15 minutes in queue, is served for 5 minutes, and leaves at 10:20 AM. The total time in the bank is 20 minutes.

Simulation Models

Two common simulation models are discussed: time-based simulation and event-based simulation.

In time-based simulation, we maintain a timeline or clock. The clock ticks (e.g., every minute), and things happen when the time reaches the moment of an event.

📌 Example: Bank opens at 9:00 AM.

• Customer C1 arrives at 9:02 AM, needs 4 minutes → leaves at 9:06 AM
• Customer C2 arrives at 9:04 AM, needs 6 minutes → leaves at 9:10 AM
• Customer C3 arrives at 9:12 AM, needs 10 minutes

The pseudo code for time-based simulation:

clock = 0;
while ( clock <= 24*60 ) {
    read new customer;
    if customer.arrivaltime == clock
        insert into shortest queue;
    check the customer at head of all four queues.
    if transaction is over
        remove from queue.
    clock = clock + 1;
}

The clock runs for 24 hours (1440 minutes). When the clock reaches a customer's arrival time, they are inserted into the shortest queue. When a transaction ends, the customer is removed. If no event occurs at a given minute, the loop simply increments the clock.

💡 Why this matters: Time-based simulation is straightforward but inefficient because the program does nothing during idle clock ticks.

In event-based simulation, we don't wait for the clock to tick until the next event. Instead, we compute the time of the next event and maintain a list of events in increasing order of time. We remove an event from the list in a loop and process it.

📌 Example events for the same scenario:

• Event 1: 2 mins — C1 enters
• Event 2: 4 mins — C2 enters
• Event 3: 6 mins — C1 leaves
• Event 4: 10 mins — C2 leaves
• Event 5: 12 mins — C3 enters

These events are stored in a special queue where the earliest event is removed first, regardless of when it was added. This requires a priority queue.

Priority Queue

A priority queue is a data structure where the dequeue operation depends not on FIFO but on some priority. In a FIFO queue, priority is given to the time of arrival — the person who comes first has higher priority. In a priority queue, elements are removed based on their priority value, not their arrival order.

🔑 Definition — Priority Queue: A data structure where each element has a priority, and elements are removed in order of their priority (highest priority first), not their insertion order. FIFO is a special case of priority queue where priority is given to arrival time.

📌 Example: In traffic, vehicles queue at a signal. When an ambulance comes from behind, it bypasses the queue and crosses the intersection first because it has higher priority.

💡 Why this matters: Priority queues are used extensively in operating systems for process scheduling, where higher-priority processes run before lower-priority ones.

Code of the Bank Simulation

The lecture presents the complete C++ implementation of the bank simulation using event-based simulation with a priority queue.

Input File Format: Each line contains: arrival time (hours, minutes) and transaction duration.

00 30 10  <- customer 1 arrives 30 min after opening, needs 10 min
00 35 05  <- customer 2 arrives 35 min after opening, needs 5 min
00 40 08
00 45 02
00 50 05
00 55 12
01 00 13
01 01 09

Key Data Structures:

Queue q[4];           // four teller queues
PriorityQueue pq;     // event list (priority queue)
int totalTime;        // total wait time for all customers
int count;            // number of customers served
int customerNo;       // customer counter

Main Driver Loop:

main (int argc, char *argv[]) {
    Customer* c;
    Event* nextEvent;
    
    ifstream data("customer.dat", ios::in);
    ReadNewCustomer(data);
    
    While( pq.length() > 0 ) {
        nextEvent = pq.remove();
        c = nextEvent->getCustomer();
        if( c->getStatus() == -1 ) {          // arrival event
            int arrTime = nextEvent->getEventTime();
            int duration = c->getTransactionDuration();
            int customerNo = c->getCustomerNumber();
            processArrival(data, customerNo, arrTime, duration, nextEvent);
        }
        else {                                 // departure event
            int qindex = c->getStatus();
            int departTime = nextEvent->getEventTime();
            processDeparture(qindex, departTime, nextEvent);
        }
    }
}

📌 Flow Explanation: The priority queue holds events. Events with status -1 are arrival events; otherwise they are departure events. Each iteration removes the earliest event (highest priority = smallest time) and processes it.

readNewCustomer Function:

void readNewCustomer(ifstream& data) {
    int hour, min, duration;
    if (data >> hour >> min >> duration) {
        customerNo++;
        Customer* c = new Customer(customerNo, hour*60+min, duration);
        c->setStatus(-1);                     // mark as new arrival
        Event* e = new Event(c, hour*60+min);
        pq.insert(e);                         // insert arrival event into priority queue
    }
    else {
        data.close();
    }
}

processArrival Function:

int processArrival(ifstream &data, int customerNo, int arrTime, int duration, Event* event) {
    int i, small, j = 0;
    // find smallest teller queue
    small = q[0].length();
    for(i=1; i < 4; i++)
        if( q[i].length() < small ) {
            small = q[i].length();
            j = i;
        }
    
    // put arriving customer in smallest queue
    Customer* c = new Customer(customerNo, arrTime, duration);
    c->setStatus(j);                        // remember which queue customer goes into
    q[j].enqueue(c);
    
    // if this is the only customer in queue, mark for departure
    if( q[j].length() == 1 ) {
        c->setDepartureTime(arrTime + duration);
        Event* e = new Event(c, arrTime + duration);
        pq.insert(e);
    }
    
    // get another customer from input
    readNewCustomer(data);
}

📌 Key Logic: The customer is placed in the shortest queue. If the queue length is exactly 1 (customer is alone at teller), a departure event is created with time = arrival time + transaction duration. A new customer is then read from the file.

processDeparture Function:

int processDeparture(int qindex, int departTime, Event* event) {
    Customer* cinq = q[qindex].dequeue();
    
    int waitTime = departTime - cinq->getArrivalTime();
    totalTime = totalTime + waitTime;
    count = count + 1;
    
    // if more customers on queue, mark next for departure
    if( q[qindex].length() > 0 ) {
        cinq = q[qindex].front();
        int etime = departTime + cinq->getTransactionDuration();
        Event* e = new Event(cinq, etime);
        pq.insert(e);
    }
}

Final Output Calculation:

double avgWait = (totalTime * 1.0) / count;
cout << "Total time:     " << totalTime << endl;
cout << "Customer:       " << count << endl;
cout << "Average wait:   " << avgWait << endl;

📌 Example: The wait time for a customer = departure time - arrival time. The totalTime accumulates wait times for all customers. Average wait = totalTime / count. If totalTime = 1500 minutes and count = 300 customers, average wait = 5 minutes.

⭐ Key Takeaways

The bank simulation demonstrates how queues and priority queues work together to model real-world systems. The priority queue is essential for event-based simulation because events must be processed in chronological order, not insertion order. The time-based simulation is simpler but inefficient as it wastes clock ticks, while event-based simulation jumps directly to the next event. The simulation code shows a practical pattern: arrival events create departure events, and each departure triggers the next customer at that teller queue to start service. Understanding these data structures and simulation techniques is critical for analyzing complex systems like bank queues, network traffic, and operating system process scheduling.

🧠 Quick Revision Questions

1. What is the key difference between time-based simulation and event-based simulation in terms of how the clock is handled?
2. In the event-based bank simulation, what does a customer's status of -1 indicate versus status values 0-3?
3. What happens in the processArrival function when the customer's queue length is exactly 1?
4. How is the average wait time calculated in the bank simulation program?
5. Why is a priority queue necessary for the event list rather than a regular FIFO queue?

📘 Lecture 11 — Implementation of Priority Queue & Tree

📖 Overview: This lecture continues the discussion of priority queue data structure, presenting its array-based implementation in C++. It then introduces tree data structures, focusing on binary trees, their mathematical definition, terminologies, and special types including strictly binary trees and complete binary trees. This knowledge is fundamental for understanding efficient searching and organization of hierarchical data.

🗂️ Topics Covered

The lecture covers the implementation of priority queue using arrays with insert, remove, and sorting operations. It then transitions to tree data structures, explaining why non-linear structures are needed. Binary trees are introduced with their recursive definition, terminologies (root, child, leaf, parent), and analysis through examples. Special types including strictly binary trees and complete binary trees are discussed with their properties, level calculations, and formulas for node counts.

📝 Lecture Summary

Implementation of Priority Queue

The priority queue is a variation of queue where elements are removed based on priority rather than FIFO order. In the banking simulation example, events were stored with their occurrence time, and the element with the earliest time was removed first. The implementation uses an array with a maximum size defined by PQMAX = 30. The class has private members for array storage, size counter, and rear index. The constructor initializes size to 0 and rear to -1. The full() method checks if size equals PQMAX and returns true if the queue is full.

🔑 Definition — Priority Queue: A data structure where elements are added to a queue and removed based on a priority value assigned to each element, rather than following First-In-First-Out order.

The remove() method first checks if size > 0. If elements exist, it retrieves the event pointer from index 0 (the first position). A for loop shifts all remaining elements one position left (from index j to j-1) to fill the gap. Then size and rear are decremented. If size becomes 0, rear is set to -1. If the queue is empty, it returns NULL and displays a message. This method is inefficient because shifting elements is time-consuming.

💡 Why this matters: The shifting operation in remove() makes this implementation slow for large queues. Better implementations using linked lists or heaps avoid this problem.

📌 Example: If the array contains events at indices 0, 1, 2 with priorities 10:00, 10:30, 11:00, removing the first event requires shifting the event at index 1 to index 0 and the event at index 2 to index 1.

The insert() method checks if the queue is not full using the full() function. If space is available, it increments rear, places the new event object at nodes[rear], increments size, then calls sortElements() to sort the array in ascending order based on event occurrence time. The method returns 1 for success or 0 for failure. The sorting ensures that the element at index 0 has the earliest (highest priority) time.

🔑 Definition — sortElements(): A method called after each insertion to arrange the array elements in ascending order according to their priority (event time), ensuring the highest priority element is at index 0.

📌 Example: Inserting a departure event at 9:45 into a queue containing events at 10:00, 10:30, and 11:00 will result in the array being sorted to [9:45, 10:00, 10:30, 11:00], making the 9:45 event available for immediate removal.

Tree

Trees are non-linear data structures where elements are not arranged in a line like stacks, queues, or linked lists. Many applications require non-linear relationships between data. The genealogy tree example shows Muhammad Aslam Khan at the top (root) with children Sohail, Javed, and Yasmeen below him, and their children further below. Unlike real trees that grow upward, data structure trees are drawn top-down for easier understanding. Trees are essential when data has hierarchical relationships that cannot be captured by linear structures.

🔑 Definition — Tree: A non-linear data structure consisting of nodes connected by edges, where data elements have parent-child relationships organized hierarchically.

💡 Why this matters: Searching in linear structures with 100,000 entries requires traversing half the list on average. Tree structures enable much faster searching.

Binary Tree

The mathematical definition states: "A binary tree is a finite set of elements that is either empty or is partitioned into three disjoint subsets. The first subset contains a single element called the root of the tree. The other two subsets are themselves binary trees called the left and right sub-trees."

🔑 Definition — Binary Tree: A tree data structure where each node has at most two subtrees, called left subtree and right subtree.

📌 Example: In the binary tree with root A, the left subtree contains nodes B, D, E, G and the right subtree contains nodes C, F, H, I. This recursive property applies at every level: node B becomes root of its subtree with left child D and right child E, while node E has left child G and empty right subtree.

A structure is NOT a tree if there are multiple paths to reach a node. For example, if node G can be reached via A-B-D-G and also via A-B-E-G, the structure becomes a graph, not a tree. Similarly, multiple links between nodes (like two connections between A and B) violate tree properties.

Terminologies of a Binary Tree

The root is the topmost node. Each node has a parent (the node above it) and children (nodes below it). Nodes can be left descendant or right descendant. Nodes with no children are called leaf nodes. The terms "descendant" and "child" are used interchangeably.

🔑 Definition — Terminologies: Root (top node), parent (node above), child (node below), left descendant (child on left), right descendant (child on right), leaf node (node with no children).

Strictly Binary Tree

A binary tree is a strictly binary tree if every non-leaf node has non-empty left and right subtrees. In other words, every node that is not a leaf must have both a left child and a right child.

🔑 Definition — Strictly Binary Tree: A binary tree where every non-leaf node has both non-empty left and right subtrees.

📌 Example: In the initial tree, node C has right child F but no left child, so it is NOT strictly binary. Adding node J as left child of C and node K as right child of E makes all non-leaf nodes (A, B, C, E, F) have both children, resulting in a strictly binary tree.

Level

The level of a node in a binary tree is defined as: root has level 0, and the level of any other node is one more than the level of its parent. The depth of a binary tree is the maximum level of any leaf in the tree.

🔑 Definition — Level: Root is at level 0; each subsequent node's level is its parent's level plus one. Depth: The maximum level among all leaves in the tree.

📌 Example: In the tree with root A at level 0, nodes B and C are at level 1, nodes D, E, F are at level 2, and nodes G, H, I are at level 3. The depth of this tree is 3.

📐 Formula: Level of node = Level of parent + 1 (for all nodes except root which is 0)

Complete Binary Tree

A complete binary tree of depth d is a strictly binary tree where all leaves are at level d. This means every level from 0 to d-1 is completely filled with nodes, and all leaf nodes are on the deepest level.

🔑 Definition — Complete Binary Tree: A strictly binary tree of depth d where all leaf nodes are at level d.

📐 Formula: Number of nodes at level k = 2ᵏ 📐 Formula: Total nodes in complete binary tree of depth d = 2ᵈ⁺¹ - 1 📐 Formula: Number of leaf nodes = 2ᵈ 📐 Formula: Number of non-leaf (inner) nodes = 2ᵈ - 1

📌 Example: In a complete binary tree of depth 3, level 0 has 2⁰ = 1 node, level 1 has 2¹ = 2 nodes, level 2 has 2² = 4 nodes, level 3 has 2³ = 8 nodes (all leaves). Total nodes = 2⁴ - 1 = 15. Leaf nodes = 2³ = 8. Non-leaf nodes = 2³ - 1 = 7.

Level of a Complete Binary Tree

If we know the total number of nodes (n) in a complete binary tree, we can calculate its depth (d).

📐 Formula: n = 2ᵈ⁺¹ - 1 → 2ᵈ⁺¹ = n + 1 → d + 1 = log₂(n + 1) → d = log₂(n + 1) - 1

📌 Example: With 100,000 nodes: d = log₂(100001) - 1 ≈ 20. So the tree would be 20 levels deep.

Operations on Binary Tree

If p points to a node in an existing tree:

• left(p) returns pointer to the left subtree
• right(p) returns pointer to the right subtree
• parent(p) returns the father of p
• brother(p) returns brother of p
• info(p) returns content of the node

These operations will be discussed in detail in the next lecture.

⭐ Key Takeaways

The priority queue does not follow FIFO rule; elements are removed based on their assigned priority values rather than insertion order. The array-based implementation of priority queue is inefficient for large datasets because removing an element requires shifting all remaining elements, and each insertion requires sorting the entire array. Trees are non-linear data structures essential for representing hierarchical relationships and enabling efficient searching operations. A binary tree's recursive nature means each node, when considered as a root, has its own left and right subtrees that are themselves binary trees. A complete binary tree of depth d has exactly 2ᵈ⁺¹ - 1 nodes with 2ᵈ leaf nodes, and its depth can be calculated as log₂(n + 1) - 1 given n total nodes.

🧠 Quick Revision Questions

1. What makes a priority queue different from a regular queue, and how does the remove() method in the array-based implementation handle this difference?
2. Why is the array-based implementation of priority queue inefficient, and what are the two specific operations that cause performance problems?
3. What is the mathematical definition of a binary tree, and how does the recursive nature of this definition apply when analyzing any node in the tree?
4. What is the difference between a strictly binary tree and a complete binary tree? Can a complete binary tree always be strictly binary, and vice versa?
5. If a complete binary tree has 31 total nodes, what is its depth, how many leaf nodes does it have, and how many non-leaf nodes?

📘 Lecture 12 — Operations on Binary Tree

📖 Overview: This lecture covers the fundamental operations on binary trees, their implementation in C++, and a practical application for searching duplicates in a list. It introduces the TreeNode class and the insert algorithm, demonstrating how binary trees can dramatically reduce the number of comparisons compared to linear data structures like linked lists.

🗂️ Topics Covered

The lecture discusses operations on binary tree including left, right, parent, brother, and info methods. It presents an application of binary trees for searching duplicates in a numerical list and explains the step-by-step process of building a binary search tree. The C++ implementation includes the TreeNode class and the insert function, followed by a detailed trace of the insertion algorithm showing how pointers move through the tree structure.

📝 Lecture Summary

Operations on Binary Tree

The lecture begins by discussing the methods of the tree data type. These methods can be classified into two categories: retrieval methods and construction methods. The retrieval methods include left(p) which returns a pointer to the left sub-tree, right(p) which returns a pointer to the right sub-tree, parent(p) which returns the father node of p, brother(p) which returns the brother node of p, and info(p) which returns the contents of node p. The construction methods include setLeft(p, x) which creates the left child node of p and sets the value x into it, and setRight(p, x) which creates the right child node of p with the info x.

Applications of Binary Tree

The binary tree is particularly useful when two-way decisions are made at each point. As an example, the lecture considers finding all duplicates in the following list of numbers: 14, 15, 4, 9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5. In addition to detecting duplicates, we may also require the frequency of numbers in the list. While a small list can be checked quickly, practical lists can range to thousands or millions of entries.

Searching for Duplicates

One approach for finding duplicates is to compare each number with all those that precede it. For example, to find duplicates for the number 4, we start scanning from the first number 14. Whenever we find the number 4, we remember the position and increment its frequency counter by 1. This comparison continues till the end of the list. However, this whole scanning process must be performed every time for each number, making it a long and time-consuming process.

A linked list can handle growth but does not reduce the number of comparisons since it is a linear data structure. To search a number in a linked list, we must begin from the start and traverse each node in linear fashion. The search operation actually becomes slower than in an array because the linked list is not contiguous.

The solution lies in using a binary tree. The binary tree is built in a special way. The first number in the list is placed in a node designated as the root. Initially, both left and right sub-trees of the root are empty. We take the next number and compare it with the number placed in the root. If it is the same, this means a duplicate. Otherwise, we create a new tree node. The new node becomes the left child if the second number is less than the root, or the right child if it is greater.

The construction process proceeds step by step:

• The first number 14 becomes the root
• Number 15 is compared with 14, found greater, and becomes the right child
• Number 4 is compared with 14, found smaller, and becomes the left child
• Number 9 is compared with 14 (smaller), then with 4 (greater), and becomes the right child of 4
• This process continues for all numbers, resulting in a complete binary tree structure

C++ Implementation of Binary Tree

The lecture presents the TreeNode class which serves as a factory for creating binary tree nodes. Since we want to use this class for different data types, it is implemented as a template class.

The class contains three private data members:

• object (type Object*) — stores the tree element (value) inside the node
• left (type TreeNode*) — stores a pointer to the left sub-tree
• right (type TreeNode*) — stores a pointer to the right sub-tree

The public methods include:

• A parameter-less constructor that initializes all data members to NULL
• A parameterized constructor that takes an object value and sets left and right to NULL
• getInfo() — returns the object (element) of the TreeNode
• setInfo(Object)* — sets the value of the object data member
• getLeft() — returns the pointer to the left sub-tree
• getRight() — returns the pointer to the right sub-tree
• setLeft(TreeNode)* — sets the pointer to the left sub-tree
• setRight(TreeNode)* — sets the pointer to the right sub-tree
• isLeaf() — returns 1 if the current node is a leaf node (both left and right are NULL), otherwise returns 0

The main program creates a root node and inserts all numbers from the list using the insert() function. The list ends with -1 as a delimiter marker.

The insert() function accepts two parameters: a pointer to a TreeNode object and the info to insert. It uses two pointer variables p and q, both initialized to point to the root. The while loop continues as long as the number to insert is not equal to the number in the current node AND q is not NULL. Inside the loop, p is assigned the value of q. If the number to insert is smaller than the number in p's node, q moves to the left child; otherwise, q moves to the right child.

After the loop terminates, if the numbers are equal, a duplicate message is displayed and the new node is deleted. If the number is less than the number in p's node, the new node is inserted as the left child; otherwise, it becomes the right child.

void insert(TreeNode<int>* root, int* info) {
    TreeNode<int>* node = new TreeNode<int>(info);
    TreeNode<int>* p, * q;
    p = q = root;
    while(*info != *(p->getInfo()) && q != NULL) {
        p = q;
        if(*info < *(p->getInfo()))
            q = p->getLeft();
        else
            q = p->getRight();
    }
    if(*info == *(p->getInfo())) {
        cout << "attempt to insert duplicate: " << *info << endl;
        delete node;
    }
    else if(*info < *(p->getInfo()))
        p->setLeft(node);
    else
        p->setRight(node);
}

Trace of insert

The lecture provides a detailed trace of inserting the number 17 into the existing tree. Initially, pointers p and q both point to the root node (containing 14). Since 17 is greater than 14, q moves to the right child (node with 15). Then p moves to where q was. This process continues: 17 is greater than 15, so q moves to the right child (node with 18). p follows. Now 17 is less than 18, so q moves to the left child (node with 16). p follows. Finally, 17 is greater than 16, so q tries to move to the right child, but it is NULL, causing the while loop to terminate. The new node with 17 is then inserted as the right child of the node with 16.

💡 Why this matters: This algorithm will be used rigorously in future lectures. Complete understanding of the pointer movements and comparison logic is essential for comprehending more complex tree implementations.

⭐ Key Takeaways

A binary tree drastically reduces the number of comparisons when searching for duplicates compared to linear data structures like linked lists or arrays. The tree is built by comparing each new number with existing nodes, placing smaller numbers to the left and larger numbers to the right, which naturally organizes data for efficient search. The insert algorithm uses two pointers (p and q) to traverse the tree, where q explores forward and p follows behind, allowing the algorithm to identify the correct insertion point when q reaches NULL. The C++ TreeNode class is implemented as a template to handle different data types and provides essential methods for tree construction and traversal. Understanding the pointer-based insertion algorithm is fundamental for all future tree-based data structures.

🧠 Quick Revision Questions

1. What are the two categories of methods for the binary tree data type, and what is the purpose of each?
2. How does the binary tree insertion algorithm decide whether to place a new node as a left child or right child?
3. In the insert() function, what causes the while loop to terminate, and what happens after termination?
4. What is the purpose of having two pointer variables p and q in the insertion algorithm instead of just one?
5. How does the isLeaf() method determine whether a node is a leaf, and what does it return in each case?

📘 Lecture 13 — Cost of Search, Binary Search Tree (BST), Traversing a Binary Tree

📖 Overview: This lecture focuses on the efficiency gains of using a binary tree over a linked list for search operations. It formally introduces the Binary Search Tree (BST) and explores the three fundamental methods for traversing a binary tree: preorder, inorder, and postorder. The C++ implementations of these traversal methods are provided, and the concept of recursion is explained in the context of tree traversal.

🗂️ Topics Covered

This lecture begins by analyzing the cost of search in a binary tree, demonstrating a significant performance advantage over a linked list for large datasets. It then formally defines a Binary Search Tree (BST), where the left subtree contains smaller values and the right subtree contains larger values. The core of the lecture explains the three methods of traversing a binary tree — preorder, inorder, and postorder — with their respective C++ code implementations. An example tree is used to illustrate the output of each traversal, with a key observation that inorder traversal produces sorted data. Finally, the concept of recursion is discussed as the mechanism enabling these traversals.

📝 Lecture Summary

Cost of Search

To find if a number exists in a binary tree, the search process goes down one level per comparison. In a tree of depth d, the maximum number of comparisons is equal to d. For a complete binary tree with n nodes, its depth d is approximately log₂(n). This means that searching a tree of 100,000 nodes requires at most about 20 comparisons, while a linked list of the same size might require up to 100,000 comparisons. The difference in time is massive: microseconds vs. hours for a billion-node structure.

🔑 Definition — Complete Binary Tree: A binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. 📐 Formula: d = log₂(n + 1) – 1 → The depth (d) of a complete binary tree with n nodes. 📌 Example: For a tree with 100,000 nodes, the depth d is calculated as log₂(100001) – 1, which is approximately 20.

💡 Why this matters: The logarithmic search time of a binary tree makes it vastly superior to a linked list for storing and searching large datasets, converting a search that takes hours into one that takes microseconds.

Binary Search Tree (BST)

A binary tree has the specific property that, for any node, all items in its left subtree are smaller than the node's value, and all items in its right subtree are larger. This structure is called a Binary Search Tree (BST). Because the data is stored in this specific order, it is also known as an ordered tree. This ordering is the foundation for the efficient search operations discussed earlier.

🔑 Definition — Binary Search Tree (BST): A binary tree with the property that the items in the left sub-tree are smaller than the root, and the items in the right sub-tree are larger than the root.

Traversing a Binary Tree

Traversing a binary tree is different from traversing a linear list because a node has two distinct children. A generic binary tree consists of three components: a root (N), a left subtree (L), and a right subtree (R). From the six possible permutations of these three components, three fundamental traversal methods are selected:

1. Preorder (N, L, R)
2. Inorder (L, N, R)
3. Postorder (L, R, N)

The C++ code for these methods uses recursion.

🔑 Definition — Preorder Traversal: Visit the root first, then traverse the left subtree, then the right subtree. 🔑 Definition — Inorder Traversal: Traverse the left subtree first, then visit the root, then the right subtree. 🔑 Definition — Postorder Traversal: Traverse the left subtree, then the right subtree, then visit the root.

C++ code

The code for these methods is short, recursive, and applies to trees of any size.

preorder method:

void preorder(TreeNode<int>* treeNode) {
    if( treeNode != NULL ) {
        cout << *(treeNode->getInfo()) << " ";
        preorder(treeNode->getLeft());
        preorder(treeNode->getRight());
    }
}

Logic: Print the node, then recursively print the left subtree, then the right subtree.

inorder method:

void inorder(TreeNode<int>* treeNode) {
    if( treeNode != NULL ) {
        inorder(treeNode->getLeft());
        cout << *(treeNode->getInfo()) << " ";
        inorder(treeNode->getRight());
    }
}

Logic: Recursively traverse the left subtree, then print the node, then recursively traverse the right subtree.

postorder method:

void postorder(TreeNode<int>* treeNode) {
    if( treeNode != NULL ) {
        postorder(treeNode->getLeft());
        postorder(treeNode->getRight());
        cout << *(treeNode->getInfo()) << " ";
    }
}

Logic: Recursively traverse the left subtree, then the right subtree, then print the node.

These are called by passing the root pointer: inorder(root);

Example

Consider a tree with the root value 14 and the following structure:

        14
       /  \
      4    15
     / \    \
    3   9    18
       /    / \
      7    16  20
     /      \
    5       17

Preorder output: 14 4 3 9 7 5 15 18 16 17 20 Explanation: Root is printed first (14). Then the entire left subtree is traversed (4, 3, 9, 7, 5), followed by the right subtree (15, 18, 16, 17, 20).

Inorder output: 3 4 5 7 9 14 15 16 17 18 20 Explanation: The left subtree is traversed first. The first number printed is the leftmost node (3). The output is in ascending sorted order.

Postorder output: 3 5 7 9 4 17 16 20 18 15 14 Explanation: The root (14) is printed last.

A key takeaway is that Inorder traversal of a BST produces a sorted list of the numbers.

Recursion is the mechanism by which these functions call themselves to traverse the subtrees. Each function call is pushed onto a run-time stack, which keeps a record of parameters, local variables, and the return address for that specific call.

📌 Example: In the inorder traversal, the function recursively calls itself for the left child of 14. It calls itself for the left child of 4, which is 3. When the function checks 3, it has no left child and its left subtree call returns. The value "3" is then printed. This shows the "left, root, right" order being implemented recursively.

⭐ Key Takeaways

The critical concept is the dramatic performance advantage of a Binary Search Tree (BST) over a linked list for search operations, achieving a search cost of O(log n) compared to O(n). You must understand the property of a BST that enables this: left subtrees hold smaller values, and right subtrees hold larger values. The three tree traversal methods (preorder, inorder, postorder) are fundamental, and you must know their order and output. The key insight is that an inorder traversal of a BST yields the data in sorted order. Finally, the recursive nature of these traversals is essential, and you should be able to walk through the algorithm's execution on a given tree.

🧠 Quick Revision Questions

1. What is the approximate depth of a complete binary tree with 1,000,000 nodes?
2. Define the property of a Binary Search Tree (BST). What makes it an "ordered tree"?
3. For the tree in Figure 13.6 of the lecture (with root 40), what is the preorder traversal?
4. Why does an inorder traversal of a BST automatically produce a sorted list of values?
5. Explain the concept of recursion as it is used in the binary tree traversal functions. How does the run-time stack manage these calls?

📘 Lecture 14 — Data Structures

📖 Overview: This lecture explores the recursive mechanisms behind binary tree traversals (preorder, inorder, and postorder) in depth, contrasting them with non-recursive implementations using explicit stacks. Understanding how recursion uses the call stack is essential for mastering tree operations and appreciating the efficiency of recursive solutions on inherently recursive data structures.

🗂️ Topics Covered

This lecture details how recursive calls are implemented using the system stack, then provides a step-by-step trace of recursive preorder and inorder traversals on a specific binary search tree. It subsequently introduces non-recursive inorder traversal using an explicit stack, compares the two approaches, and previews level-order traversal as a breadth-oriented alternative to depth-first methods.

📝 Lecture Summary

Recursive Calls

Function calls, whether to another function or recursively to itself, use the system stack to store parameters, return addresses, and local variables. When a called function finishes, the stored return address is used to resume execution of the caller. Recursion is implemented with the same stack mechanism as any other function call.

🔑 Definition — Recursion: A technique where a function calls itself to solve a smaller instance of the same problem, relying on a terminating condition to stop.

Preorder Recursion

In preorder traversal, the node's value is printed before traversing its left and right subtrees. Starting at the root (14), the value is printed. The function then calls itself recursively on the left subtree (node 4), prints 4, and continues to the left subtree of 4 (node 3), printing 3. The left subtree of 3 is NULL, which acts as the terminating condition — the recursion stops on that branch. After a NULL left subtree is encountered at node 3, the return address from the stack takes control back to node 3, and its right subtree (also NULL) is checked. Control returns to node 4, whose right subtree (node 9) is then traversed in preorder. This pattern of pushing calls onto the stack (indicated by increasing dots in figures) and popping them upon return continues until all nodes are visited.

📐 Terminology: The pattern for preorder is: Root → Left subtree → Right subtree.

📌 Example: On the given tree (root 14), the preorder recursion prints: 14, 4, 3, 9, 7, 5 after traversing the left subtree of 14. The right subtree (starting with 15) prints: 15, 18, 16, 17, 20, completing the full preorder output: 14, 4, 3, 9, 7, 5, 15, 18, 16, 17, 20.

💡 Why this matters: The recursive call stack mirrors the tree's structure, pushing deeper as we descend and popping back as we return — a natural fit for hierarchical data.

Inorder Recursion

In inorder traversal, the node’s value is printed after traversing its left subtree but before traversing its right subtree. Starting with root 14, the function recursively calls itself on the left subtree (node 4), which in turn calls on its left subtree (node 3). From node 3, its left subtree is NULL — the terminating condition. After returning from NULL, the node (3) is printed, then its right subtree (NULL) is checked. Control returns to node 4, which prints 4 after its left subtree is done. The recursion proceeds to the right subtree (node 9), following the same pattern: traverse left (to 7 then 5), print when left is NULL, then traverse right. After completing node 4's subtree, control returns to root 14, which is printed. The same pattern is applied to the right subtree (15 → 18 → 16 → 17 → 20).

📐 Terminology: The pattern for inorder is: Left subtree → Root → Right subtree.

📌 Example: On the given tree, the inorder traversal prints: 3, 4, 5, 7, 9, 14, 15, 16, 17, 18, 20 — a sorted ascending sequence, as expected from a binary search tree.

💡 Why this matters: Inorder traversal of a binary search tree always yields sorted output, making it invaluable for retrieval and sorting operations.

Non-Recursive Traversal

Non-recursive traversal replaces the system's call stack with an explicit stack created by the programmer. For inorder, the algorithm uses a Stack<TreeNode<int>*> to store nodes. A pointer p starts at the root. An inner while loop pushes all nodes along the leftmost path (root, then left child, then its left child, etc.) onto the stack. When a left child is NULL, the loop exits. A node is popped from the stack, its value printed, and p is set to its right child. The outer loop repeats until the stack is empty and p is NULL.

🔑 Definition — Explicit stack: A user-defined stack data structure that the programmer manually manages to store and retrieve nodes during iteration.

📌 Example: On the tree with root 14, the explicit stack pushes 14, 4, 3 in sequence. After exiting the inner loop (left of 3 is NULL), 3 is popped and printed. Then 4 is popped and printed. Then nodes 9, 7, 5 are pushed; 5 is popped and printed; 7 popped; 9 popped; 14 popped; then 15, 18, 16, 17, 20 are processed similarly.

📐 Comparison: Recursive inorder uses inorder(14), inorder(4), inorder(3)... while non-recursive uses push(14), push(4), push(3).... The only difference is the function name vs. push operation — the logic is identical.

Traversal Trace

Comparing recursive and non-recursive inorder shows no difference in the order of node processing. Both use the stack data structure: recursive uses the system stack implicitly; non-recursive uses an explicit stack. The recursive version is more readable (3-4 lines vs. many lines for non-recursive) and is often more efficient for recursive data structures because the stack operations are highly optimized at the assembly level. Program readability is crucial — well-commented, clean code is easier to debug and maintain.

🔑 Definition — Readability: The ease with which a human can understand the logic and flow of a program, often enhanced by recursive solutions on recursive data structures.

Level-Order Traversal

Level-order traversal visits nodes level by level, from left to right, in contrast to depth-first traversals (preorder, inorder, postorder). It is not recursive but breadth-oriented.

📌 Example: On the given tree, level-order traversal visits: 14 (level 0), then 4, 15 (level 1), then 3, 9, 18 (level 2), then 7, 16, 20 (level 3), then 5, 17 (level 4). Output: 14, 4, 15, 3, 9, 18, 7, 16, 20, 5, 17.

💡 Why this matters: Level-order is used in algorithms that require processing nodes by depth, such as printing trees visually or finding shortest paths in unweighted graphs (when applied to trees).

⭐ Key Takeaways

All depth-first traversals (preorder, inorder, postorder) are naturally implemented recursively, leveraging the system stack. The specific order of visiting the root relative to left and right subtrees defines each traversal type. A non-recursive inorder traversal using an explicit stack produces the same output as its recursive counterpart. Recursive solutions are generally preferred for recursive data structures due to superior readability and often-equal or better efficiency. A terminating condition is mandatory to prevent infinite recursion and stack overflow. Level-order traversal, in contrast, visits nodes level by level.

🧠 Quick Revision Questions

1. What is the terminating condition for recursive tree traversals, and why is it essential?
2. Trace the first five steps (nodes visited and order) of preorder traversal on a tree with root 10, left child 5, right child 15, left child of 5 = 2, right child of 5 = 7.
3. Explain how the explicit stack is used in non-recursive inorder traversal. What is pushed, when, and what is the LIFO implication?
4. Compare and contrast the recursive inorder and non-recursive inorder traversals in terms of readability and efficiency.
5. What is the key difference between depth-first traversals (preorder, inorder, postorder) and level-order traversal in terms of node visitation order?

📘 Lecture 15 — Data Structures

📖 Overview: This lecture explores level-order traversal of binary trees using queues, demonstrates how to store non-integer data types like strings in binary search trees, and covers the complex operation of deleting nodes from a BST. Understanding these concepts is crucial for mastering tree operations in real-world applications like sorting and directory management.

🗂️ Topics Covered

The lecture covers level-order traversal of a binary tree using a queue data structure with step-by-step execution on a sample tree, storing other types of data in binary trees including strings, building a binary search tree (BST) with strings using lexicographic comparison and the strcmp function, and the three cases of deleting a node from a BST: leaf nodes, nodes with one child, and nodes with two children requiring inorder successor replacement.

📝 Lecture Summary

Level-order Traversal of a Binary Tree

In the last lecture, we implemented tree traversal in preorder, postorder, and inorder using recursive and non-recursive methods. Level-order traversal prints the binary tree level by level, starting from the root and moving to each subsequent level. In the example tree shown in Fig 15.1, at the first level there is only node 14; at the second level, nodes 4 and 15; at the third level, 3, 9, and 18; at the fourth level, 7, 16, and 20; and at the fifth and final level, nodes 5 and 17. The output of level-order traversal for this tree would be: 14 4 15 3 9 18 7 16 20 5 17.

Surprisingly, the implementation of level-order traversal is simple using a non-recursive method and by employing a queue instead of a stack. A queue is a FIFO (First-In-First-Out) structure, which makes level-order traversal easier because levels come turn by turn.

void levelorder( TreeNode <int> * treeNode ) 
{ 
    Queue <TreeNode<int> *> q; 
    if( treeNode == NULL ) return; 
    q.enqueue(treeNode); 
    while( !q.empty() ) 
    { 
        treeNode = q.dequeue(); 
        cout << *(treeNode->getInfo()) << " "; 
        if(treeNode->getLeft() != NULL ) 
            q.enqueue( treeNode->getLeft()); 
        if(treeNode->getRight() != NULL ) 
            q.enqueue( treeNode->getRight()); 
    } 
    cout << endl; 
}

The method levelorder accepts a pointer of type TreeNode <int>. It first creates a queue q containing TreeNode<int>* objects. If treeNode is NULL, the method returns immediately. Otherwise, the first node is added to the queue. The while loop runs until the queue becomes empty. Inside the loop, a node is dequeued and its integer value is printed. Then, if the left subtree exists, it is inserted into the queue, and if the right subtree exists, it is also inserted.

💡 Why this matters: The selection of appropriate data structure is very critical for a successful solution. Without using the queue data structure, the problem of level-order tree traversal would not have been so easy. The turn-by-turn nature of levels guided us to use a queue.

🔑 Definition — Level-order traversal: A tree traversal method that visits nodes level by level from top to bottom, left to right, using a queue data structure.

📐 Queue operation: enqueue → add to back; dequeue → remove from front → enables FIFO processing of tree levels.

📌 Example: For the tree with root 14, left child 4, right child 15, and their subtrees, the level-order traversal proceeds as:

• Queue: [14] → dequeue 14, print "14", enqueue 4 and 15 → Queue: [4, 15]
• Dequeue 4, print "4", enqueue 3 and 9 → Queue: [15, 3, 9]
• Dequeue 15, print "15", enqueue 18 → Queue: [3, 9, 18]
• Dequeue 3, print "3", no children → Queue: [9, 18]
• Dequeue 9, print "9", enqueue 7 → Queue: [18, 7]
• Continue until queue is empty → Output: 14 4 15 3 9 18 7 16 20 5 17

Storing Other Types of Data in Binary Tree

Until now, we have placed int numbers in tree nodes because they were easier for sorting and comparison problems. However, we can put any data type in tree nodes depending upon the problem. For example, if we want to enter the names of people in a telephone directory, we build a binary tree of strings.

Binary Search Tree (BST) with Strings

Let's write C++ code to insert non-integer data in a binary search tree. The function wordTree() constructs a root tree node containing char type data, then creates a static character array word containing words like "babble", "fable", etc., with NULL as the last element. The first word is placed in the root node, and a for loop inserts the remaining words using the insert method until a NULL is encountered. After insertion, the inorder() method prints the tree node elements in sorted order.

The insert(TreeNode<char> * root, char * info) method accepts a pointer to a TreeNode containing char type elements and a pointer to char for the new word. It creates a new TreeNode with the info value and declares two pointers p and q of type TreeNode<char>, both initially pointing to root.

For string comparison, we use the lexicographic order based on ASCII values. For example, the ASCII value of 'B' (66) is greater than 'A' (65), so 'B' is greater than 'A'. Similarly, a word starting with 'A' is smaller than words starting with 'B' or any other character up to 'Z'.

The strcmp function from the standard C library compares two strings. It takes info as the first parameter and returns: a negative number if info is smaller, 0 if both are equal, and a positive number if info is greater.

Inside the while loop, strcmp compares info with the value in the node pointed to by p. The loop terminates when a duplicate is found (strcmp returns 0) or when q points to NULL. If the new word is smaller, we traverse to the left subtree; otherwise, we go to the right subtree. After the loop, if duplication is found, a message is displayed and the new node is deleted. Otherwise, the new node is inserted to the left or right of the current node based on comparison.

The output of inorder traversal on the tree built from the word array is:

abandon
abash
accuse
adhere
advise
babble
backup
bandit
cease
chain
daily
debunk
eagle
economy
fable
feeder
fetch
gain
genius
jacket

Notice the words are printed in sorted increasing order. Building a binary search tree and doing an inorder traversal leads to a sorting algorithm.

🔑 Definition — Lexicographic order: The ordering of strings based on the ASCII values of their characters, where 'A' < 'B' < ... < 'Z' and shorter strings typically precede longer ones when they share a common prefix.

📐 strcmp function: strcmp(string1, string2) returns negative if string1 < string2, 0 if equal, positive if string1 > string2.

📌 Example: When inserting "babble" (root), then "fable" (greater, right), then "jacket" (greater, right of "fable"), then "backup" (less than "fable" but greater than "babble", so left of "fable" and right of "babble"), the tree is built following BST rules. Inorder traversal produces the sorted output shown above.

Deleting a Node From BST

Deletion is often the hardest operation with many data structures. Once we have found the node to be deleted, we need to consider several possibilities.

Case 1: The node is a leaf — It can be deleted quite easily. For example, deleting node containing number 3 (a leaf node) simply requires deleting it and pointing the parent's right subtree pointer to NULL.

Case 2: The node has one child — The node can be deleted after its parent adjusts a pointer to bypass the node and connect to the inorder successor. For example, deleting node containing number 4 requires adjusting the right subtree pointer in the node containing value 2 to point to the inorder successor of 4. The important point is that the inorder traversal order must be maintained after the delete.

Case 3: The node has both left and right subtrees — This is more complicated. The strategy is to replace the data of this node with the smallest data of the right subtree (the inorder successor) and recursively delete that node.

Consider deleting the node containing number 2 from a tree. The inorder traversal gives: 1, 2, 3, 4, 5, 6, 8. First, find the leftmost node in the right subtree of node 2, which is node containing number 3. Copy the contents of this leftmost node (3) to the node to be deleted (2). Then delete the original leftmost node containing value 3. Since this node has no left subtree but may have a right subtree, its deletion follows Case 2. After deletion, inorder traversal gives: 1, 3, 4, 5, 6, 8 — still sorted.

🔑 Definition — Inorder successor: The node that comes immediately after a given node in an inorder traversal of a binary search tree; it is the leftmost node in the right subtree of the node to be deleted.

📌 Example: Deleting node 2 (with both children) from a BST containing values 1, 2, 3, 4, 5, 6, 8:

1. Find inorder successor of 2 → leftmost node in right subtree → node containing 3
2. Copy 3 to node 2's position
3. Delete the original node containing 3 (now a leaf or one-child node)
4. Tree maintains BST property and inorder traversal yields sorted order: 1, 3, 4, 5, 6, 8

⭐ Key Takeaways

Level-order traversal is efficiently implemented using a queue data structure in a non-recursive manner, where nodes are processed level by level in FIFO order — this demonstrates the critical importance of selecting appropriate data structures during the design phase before writing code. Binary search trees can store any data type, including strings, using appropriate comparison functions like strcmp for lexicographic ordering, and performing an inorder traversal on such a BST produces a sorting algorithm. Deleting nodes from a BST requires handling three distinct cases: leaf nodes (simple deletion), nodes with one child (bypass with parent pointer adjustment), and nodes with two children (replace with inorder successor and recursively delete that successor). The inorder traversal of a BST always produces sorted output, whether the tree contains integers or strings, making it a fundamental property for sorting and searching operations. When deleting a node with two children, the key strategy is to copy the inorder successor's data to the target node and then delete the successor node, which ensures the BST property is preserved.

🧠 Quick Revision Questions

1. What data structure is used for level-order traversal and why is it more suitable than a stack?
2. How does the preorder traversal differ from level-order traversal in terms of node visit order?
3. In the string BST insertion, what function is used to compare strings and what are its possible return values?
4. What are the three cases for deleting a node from a BST, and what strategy is used for the case where a node has both children?
5. Why does inorder traversal of a binary search tree always produce sorted output regardless of the data type?

📘 Lecture 16 — Deleting a Node in BST & Binary Search Tree Class

📖 Overview: This lecture covers the complete procedure for deleting nodes from a Binary Search Tree (BST), handling three distinct cases. It also presents the full C++ implementation of the remove method, the findMin helper function, and the complete Binary Search Tree class definition with its interface and implementation files.

🗂️ Topics Covered

The lecture begins with a detailed explanation of the three cases for deleting a node from a BST: leaf node deletion, node with one child, and node with two children (using inorder successor replacement). It then presents the complete C++ code for the remove method and the findMin function, explaining recursion and tail recursion. Finally, it introduces the complete Binary Search Tree Class including its header file (BinarySearchTree.h) with the BinaryNode class definition, the implementation file (BinarySearchTree.cpp), and a test program.

📝 Lecture Summary

Deleting a node in BST

There are three cases for deleting a node from a BST. Case I: The node to be deleted is a leaf node (no children). This is the simplest case—you make the pointer in the parent node pointing to this node NULL and release the dynamically allocated memory. Case II: The node to be deleted has either a left child (subtree) or a right child (subtree). Case III: The node to be deleted has both left and right children. This is the most difficult case. The strategy is to find the inorder successor of the node to be deleted, which is the smallest element in the node’s right subtree. You copy the inorder successor’s value into the node to be deleted, then delete the inorder successor node (which will fall under Case I or Case II).

🔑 Definition — Inorder Successor: The node that appears next in an inorder traversal of a BST. For a node with two children, the inorder successor is the leftmost (minimum) node in its right subtree.

📌 Example: To delete node 2 from a BST (which has children 1 on left and 5 on right), find the inorder successor by going to the right subtree (rooted at 5) and finding the smallest element—this is node 3. Copy value 3 into node 2. Now node 3 (the inorder successor) must be deleted. Since node 3 has only a right child (node 4), this falls under Case II. Connect node 5's left pointer directly to node 4, deleting node 3.

C++ code for remove

The method is named remove because delete is a reserved keyword in C++. The remove method returns a pointer to TreeNode and takes two arguments: a pointer to the root of the tree (TreeNode<int>* tree) and an integer info (the value to delete). A temporary variable cmp is computed as info - *(tree->getInfo()). If cmp < 0, the node is in the left subtree; the method calls remove recursively on the left child and reassigns the left pointer. If cmp > 0, the node is in the right subtree, and the method calls remove recursively on the right child. If the node has two children (checked with tree->getLeft() != NULL && tree->getRight() != NULL), the method finds the minimum node in the right subtree using findMin, copies its value into the current node, and then recursively removes that minimum node from the right subtree. The else block handles the cases where the node has zero or one child—it saves the node to delete, replaces it with its non-NULL child (or NULL if both are NULL), and then deletes the original node.

🔑 Definition — Tail Recursion: A recursive call that appears as the last statement in a function. It can be replaced with a loop to eliminate the recursion stack overhead.

📌 Example: The findMin method is implemented with tail recursion. It checks if tree == NULL (return NULL), or if tree->getLeft() == NULL (return tree as the minimum), otherwise it recursively calls findMin(tree->getLeft()). This can be rewritten as an iterative loop that traverses left children until reaching a node with a NULL left pointer.

Binary Search Tree Class (BST)

The BST class is implemented with a header file (BinarySearchTree.h) containing the interface and a separate implementation file (BinarySearchTree.cpp). The .h file uses conditional compilation with #ifndef, #define, and #endif to prevent multiple inclusions. It contains a forward declaration of BinarySearchTree before defining BinaryNode. The BinaryNode class stores an element (template type EType), and pointers left and right. Its constructor uses an initialization list to set element(theElement), left(lt), and right(rt). The BinarySearchTree class is declared as a friend of BinaryNode, allowing it to access private members. The public interface includes constructors, destructor, findMin, findMax, find, isEmpty, printTree, insert, remove, and assignment operator. Private helper methods have different signatures (including the tree root pointer as an additional parameter). The ITEM_NOT_FOUND constant is used to signal failed finds. The implementation file provides method bodies, including a recursive findMin, an iterative findMax, and a clone method for deep copying. A test program inserts numbers 1 to 30, prints the tree, removes all even numbers, and prints the resulting tree.

🔑 Definition — Forward Declaration: A declaration that tells the compiler a class exists before its full definition, allowing it to be referenced by other classes (e.g., as a friend).

🔑 Definition — Initialization List: In C++, the list after the colon in a constructor that initializes member variables by calling their constructors explicitly, rather than assigning values inside the constructor body.

💡 Why this matters: The friend declaration between BinaryNode and BinarySearchTree is necessary because BinarySearchTree needs direct access to node internals (for efficient tree operations) while keeping those details hidden from external users.

⭐ Key Takeaways

Students must understand the three deletion cases for BST: leaf (simply remove), one child (replace with that child), and two children (replace with inorder successor, then recursively delete successor). The remove method code uses recursion to traverse the tree, compares using cmp, and handles each case with specific logic. The findMin function demonstrates tail recursion (which can be replaced by iteration) and locates the leftmost node. The complete BST class uses templates for genericity, separates interface (.h) from implementation (.cpp), and employs C++ features like forward declarations, friend classes, and initialization lists. The public methods are simple wrappers that call private recursive helpers.

🧠 Quick Revision Questions

1. What are the three cases for deleting a node from a Binary Search Tree, and how does the algorithm differ for each?
2. How is the remove method implemented in C++ to handle the case where a node has two children? What is the role of the findMin function?
3. What is an inorder successor, and why is the inorder successor guaranteed to have at most one child?
4. In the BinarySearchTree class, why is BinarySearchTree declared as a friend of BinaryNode? What purpose does the forward declaration serve?
5. How does the findMin method work recursively, and how can its tail recursion be replaced with an iterative loop?

📘 Lecture 17 — Reference Variables

📖 Overview: This lecture explains the concept of reference variables in C++ and how they differ from call by value and call by pointer mechanisms. Understanding reference variables is crucial for efficient function calls that avoid costly copying of large objects while maintaining clean syntax.

🗂️ Topics Covered

Reference variables are introduced as a mechanism to pass arguments to functions without making copies or using pointer syntax. The lecture compares three function calling methods: call by value, call by pointer, and call by reference, using detailed call stack diagrams to illustrate how each method affects the original variable. A sample program demonstrates these concepts with concrete examples.

📝 Lecture Summary

Reference Variables

The & symbol has two distinct uses in C++. When placed before a variable name (e.g., &x), it is the address operator that returns the memory address of that variable. When placed after the type in a function parameter (e.g., int& x), it declares a reference variable.

🔑 Definition — Address Operator (&): Returns the memory address of the variable it precedes. For example, int* ptr = &x; stores the address of variable x in pointer ptr.

🔑 Definition — Reference Variable: A parameter declared with & after its type (e.g., int& oldVal) that acts as an alias to the original variable passed from the calling function.

The lecture presents three function examples to illustrate different argument passing methods:

Function 1 - Call by Value (intMinus1):

int intMinus1( int oldVal) {
    oldVal = oldVal – 1;
    return oldVal;
}

This function takes an integer argument by value. A copy of the argument is made on the call stack.

Function 2 - Call by Pointer (intMinus2):

int intMinus2( int* oldVal) {
    *oldVal = *oldVal – 2;
    return *oldVal;
}

This function takes a pointer to integer as argument. The *oldVal notation is dereferencing, which accesses the value at the memory location pointed to by oldVal.

Function 3 - Call by Reference (intMinus3):

int intMinus3( int& oldVal) {
    oldVal = oldVal – 3;
    return oldVal;
}

The & after the type indicates this is a reference variable. No & or * is needed in the function body.

Internal Memory Organization of a Process

When a program runs, it becomes a process and is allocated a block of memory partitioned into several areas: Code (compiled binary), Static data (global/static variables), Stack (used for function calls), and Heap (dynamic memory allocation via new operator).

The call stack is used during function calls. When a function is called, an activation record is created containing parameters, local variables, and return address. A stack pointer (sp) points to the top of the stack.

Call Stack Analysis for intMinus1 (Call by Value)

When intMinus1(myInt) is called with myInt = 31, a copy of myInt (value 31) is placed on the stack as the parameter oldVal of the called function. The function subtracts 1 from oldVal (making it 30), but the original myInt in the caller remains unchanged at 31. After the function returns, the activation record is popped from the stack, and the return value (30) is assigned to retVal.

📌 Example: With myInt = 31, calling intMinus1(myInt) results in myInt = 31 and retVal = 30. The original variable remains unchanged.

💡 Why this matters: Call by value protects the original data but creates copies, which can be inefficient for large objects.

Call Stack Analysis for intMinus2 (Call by Pointer)

When intMinus2(&myInt) is called, the address of myInt (1072) is passed as the pointer value. The function uses *oldVal = *oldVal – 2, which accesses the memory location 1072 (where myInt is stored) and changes its value from 31 to 29. Thus, myInt is permanently changed.

📌 Example: With myInt = 31, calling intMinus2(&myInt) results in myInt = 29 and retVal = 29. The original variable is modified.

Call Stack Analysis for intMinus3 (Call by Reference)

When intMinus3(myInt) is called, the reference variable oldVal becomes another name for the same memory location as myInt (address 1072). The statement oldVal = oldVal – 3 directly modifies myInt's value from 31 to 28. No copy is made on the stack; oldVal simply refers to the same memory location.

📌 Example: With myInt = 31, calling intMinus3(myInt) results in myInt = 28 and retVal = 28. The original variable is modified via an alias.

🔑 Definition — Call by Reference: A function calling mechanism where the called function receives a reference (alias) to the original variable, allowing direct modification of the caller's variable without making copies or using pointer syntax.

Advantages of Reference Variables

Reference variables solve two problems: (1) Avoiding expensive copies of large objects (e.g., a 500-byte Customer object) that would consume stack space and time, and (2) Avoiding the complex syntax of pointers. The compiler implements reference variables internally using pointers, handling address calculation and dereferencing automatically behind the scenes.

💡 Why this matters: For large objects, call by value creates costly copies on the stack. Reference variables provide the efficiency of pointers without the syntax complexity.

Sample Program

The lecture provides a complete program demonstrating all three calling methods with myInt = 31. The output confirms:

• intMinus1: retVal = 30, myInt = 31 (unchanged)
• intMinus2: retVal = 29, myInt = 29 (changed)
• intMinus3: retVal = 28, myInt = 28 (changed)

⭐ Key Takeaways

The three function calling methods—call by value, call by pointer, and call by reference—each handle arguments differently in terms of copying, modification ability, and syntax. Call by value protects original data but creates copies. Call by pointer allows modification but requires complex syntax. Call by reference provides the efficiency of pointers without their complex syntax, making it ideal for passing large objects. The compiler implements references internally using pointers, so address manipulation happens behind the scenes. Understanding when to use each method is essential for writing efficient and readable C++ code, particularly when designing class interfaces that accept parameters.

🧠 Quick Revision Questions

1. What is the difference between &x (address operator) and int& x (reference variable) in C++?
2. In call by value, what happens to the original variable in the calling function when the called function modifies its parameter?
3. How does the call stack differ when passing a variable by pointer versus passing it by reference?
4. Why might call by reference be preferred over call by value for passing large objects like a Customer class?
5. What does the compiler do internally to implement reference variables, and how is this hidden from the programmer?

📘 Lecture 18 — Reference Variables, const Keyword, and Tips

📖 Overview: This lecture explores the pitfalls of storing references to transient objects in data structures and explains why dynamic memory allocation is necessary for objects that must persist beyond function scope. It also introduces the const keyword and its common uses in function signatures, along with practical tips for working with references in C++.

🗂️ Topics Covered

The lecture revisits reference variables and their behavior with the call stack, then demonstrates the problem of storing references to local (transient) objects in a queue. It explains how dynamic memory allocation on the heap solves this issue, and illustrates memory organization with stack and heap growth directions. Finally, it introduces the const keyword and provides several tips for using references safely.

📝 Lecture Summary

Reference Variables

In the last lecture we discussed about reference variables, seeing three examples: call by value, call by reference, and call by pointer. We saw the use of stack when a function is called by value, by reference, or by pointer. The arguments passed to the function and local variables are pushed onto the stack. There is one important point to note that in this course, we are using C/C++ but the usage of stack is similar in most computer languages like FORTRAN and Java. The syntax we are using here is C++ specific, like we are sending a parameter by pointer using & sign. In Java, native data types like int, float are passed by value and objects are passed by reference. In FORTRAN, every parameter is passed by reference. In PASCAL, you can pass a parameter by value or by reference like C++. You might have heard of ALGOL, which provided another way of passing parameters called call by name.

We have discussed when the variables are passed by reference then behind the scene what goes on inside the stack. There are few important things to take care of while using reference variables: One should be careful about transient objects that are stored by reference in data structures. We know that the local variables of a function are created on call stack. Those variables are created inside the function, remain in memory until the control is inside the function, and are destroyed when the function exits. The activation record comprises function call parameters, return address, and local variables. The activation record remains inside stack until the function is executing and is destroyed once the control is returned from the function.

Let’s see the following code that stores and retrieves objects in a queue:

void loadCustomer( Queue & q)
{
  Customer c1("irfan");
  Customer c2("sohail");
  q.enqueue( c1 );
  q.enqueue( c2 );
}

The above function loadCustomer(Queue &) accepts a parameter of type Queue by reference. Inside the function body, we create c1 and c2 Customer objects initialized to string values "irfan" and "sohail". Then we queue up these objects using the enqueue() method and the function returns. The objects created inside are local variables created on stack. In the Bank example, for each customer we have the name (32 characters maximum), arrival time (int type, 4 bytes), transaction time (int type), and departure time (int type), so the size of the Customer object is 44 bytes. The c1 and c2 objects are created on stack and have 44 bytes occupied. We are referring each 44 bytes of allocation with the name of the object.

Now consider the serviceCustomer() method:

void serviceCustomer( Queue & q)
{
  Customer c = q.dequeue();
  cout << c.getName() << endl;
}

The serviceCustomer(Queue &) also accepts one parameter of type Queue by reference. In the first statement, it takes out one element from the queue and assigns it to newly created object c. Before assignment, the object c is constructed by calling the default constructor. In the next statement, c.getName() function call is to get the name of the customer and then print it. This statement will not work. The reason is that objects c1 and c2 were created locally in loadCustomer() on stack. Their addresses (not the objects themselves) were added to the queue q. When loadCustomer() returned, the local objects c1 and c2 were destroyed but their addresses remained in the queue. When serviceCustomer() is called, the address of the object is retrieved from the queue and assigned to another local object c, but calling getName() using that retrieved address fails because the original object no longer exists.

This shows that using references alleviates the burden of copying objects, but storing references of transient objects (objects created on stack) can create problems because the transient object is destroyed when the function execution finishes.

💡 Why this matters: Transient objects are destroyed when their function returns, so storing their addresses in data structures creates dangling references that cause program crashes.

The solution is dynamic memory allocation. All variables or objects created in a function that we want to access later are created on memory heap (sometimes called free store) using the new operator. Heap is an area in computer memory that is allocated dynamically. All objects created using new must be explicitly destroyed using the delete operator.

The modified code of loadCustomer():

void loadCustomer( Queue & q)
{
  Customer * c1 = new Customer("irfan");
  Customer * c2 = new Customer("sohail");
  q.enqueue( c1 ); // enqueue takes pointers
  q.enqueue( c2 );
}

This time, we create objects using the new operator and assign starting addresses to c1 and c2 pointers. Anonymous objects (objects accessed by pointers) are created. Here c1 and c2 are pointers to the objects, not the actual objects themselves. These starting addresses are queued using enqueue(). As the objects lie on the heap, there will not be any problem and the objects will be accessible after loadCustomer() returns.

The pointer variables c1 and c2 are created on stack and will be destroyed after loadCustomer()'s activation record is destroyed. The actual objects on heap persist. Since the starting addresses of the objects are put in the queue, they remain available to use later after retrieving them from the queue using dequeue(). These dynamic objects will live in memory (on heap) unless explicitly deleted.

🔑 Definition — Heap (memory area): An area in computer memory given to a process from the operating system when the process does dynamic memory allocation.

The memory organization of a process includes: code section, static data section, stack (grows downward), and heap (grows upward). Stack grows downward and heap grows upward. An endless recursive call would cause the stack to grow and potentially overwrite the heap section. Endless dynamic memory allocation causes the heap to grow upward, potentially overwriting the stack. If a process has destructive code, it only causes its own destruction, not harming other processes. However, viruses often exploit stack overflow to change memory contents.

Consider allocating an array of 100 elements of Customer objects dynamically. Each object is 44 bytes, so the size of memory allocated on heap will be 4400 bytes (44 * 100). In the heap layout during call to loadCustomer, the object with string "irfan" is from memory address 600 to 643, and the object with name "sohail" is from address 644 to 687. When these objects are inserted in the queue, only their starting addresses (600 and 643) are inserted.

The serviceCustomer() function for dynamic objects:

void serviceCustomer( Queue & q)
{
  Customer* c = q.dequeue();
  cout << c->getName() << endl;
  delete c; // the object in heap dies
}

We take a pointer out of the queue, call the method using -> operator, and then use delete to deallocate the object. This method executes successfully because the object was created dynamically inside loadCustomer().

🔑 Definition — Dangling pointer: A pointer to an object that has already been deallocated or released. Accessing such a pointer (calling any of its members) may cause the program to crash.

The const Keyword

The const keyword is used for something to be constant. The actual meanings depend on where it occurs, but it generally means something is to be held constant. There can be constant functions, constant variables, or constant parameters.

References are pointers internally — they are constant pointers. You cannot perform any kind of arithmetic manipulation with references that you normally do with pointers. The const keyword is often used in function signatures (also called function prototypes), which mention the function name, its parameters, and return type.

Common uses of const:

1. The const keyword appears before a function parameter. For example, in a chess program:

   int movePiece(const Piece & currentPiece)
   

   The function movePiece() is passed one parameter by reference. By writing const, we are saying that the parameter must remain constant for the life of the function. If we try to change its value (e.g., the parameter appears on the left side of an assignment), the compiler will generate an error. This also means that if the parameter is passed to another function, that function must not change it either.

🔑 Definition — const parameter: A function parameter that cannot be modified within the function or by any function it is passed to.

Use of const with reference parameters is very common. This is puzzling: why are we passing something by reference and then making it constant (don't change it)? Doesn't passing by reference mean we want to change it? The answer will be discussed in the next lecture.

Tips

• The arithmetic operations we perform on pointers cannot be performed on references. • Reference variables must be declared and initialized in one statement. • To avoid dangling reference, don't return the reference of a local variable (transient) from a function. • In functions that return reference, return global, static, or dynamically allocated variables. • Reference data types are used as ordinary variables without any dereference operator. We normally use arrow operator (->) with pointers. • const objects cannot be assigned any other value. • If an object is declared as const in a function, then any further functions called from this function cannot change the value of the const object.

⭐ Key Takeaways

Storing references to transient (stack-allocated) objects in data structures causes problems because those objects are destroyed when the function exits, creating dangling references. To preserve objects beyond function scope, use dynamic memory allocation with the new operator to create objects on the heap; their addresses can then be safely stored in data structures. Remember that pointer variables themselves are destroyed when the function returns, but the heap-allocated objects persist until explicitly deleted with delete. The const keyword is used to make function parameters immutable, and it's commonly combined with reference parameters for efficiency without allowing modification. Avoid dangling references by never returning references to local variables.

🧠 Quick Revision Questions

1. What is a transient object and why is it problematic to store its reference in a data structure?
2. How does dynamic memory allocation using new solve the problem of transient objects?
3. What is the difference between a pointer variable (created on stack) and the actual object it points to (created on heap)?
4. Why might passing a parameter by reference with the const keyword be useful?
5. What is a dangling pointer and what can cause one?

📘 Lecture 19 — Data Structures

📖 Overview: This lecture explores the use of the const keyword in C++ to enforce programming discipline, examines the problem of degenerate binary search trees that form from sorted data, and introduces AVL trees as a self-balancing solution to maintain efficient search operations. Understanding these concepts is crucial for writing robust, efficient data structure implementations.

🗂️ Topics Covered

The lecture covers three main topics: the usage of the const keyword in function parameters, return types, and member functions to prevent unintended modifications; degenerate binary search trees that occur when data is inserted in sorted order, causing the tree to resemble a linked list; and AVL trees, which maintain balance by ensuring the height difference between left and right subtrees is at most 1 at every node.

📝 Lecture Summary

Usage of const keyword

The const keyword is used in several ways to enforce programming discipline and prevent accidental modifications. When passing parameters by reference, using const allows read-only access without copying the object. This is efficient because it avoids the time and memory overhead of creating a copy via the copy constructor, while ensuring the function cannot alter the original object. The calling function has read-only access to this object, using it in computation but not changing it.

🔑 Definition — const reference parameter: A reference parameter declared with const that allows a function to access an object without copying it and without being able to modify it, providing both efficiency and safety.

When const appears at the end of a class member function signature, such as EType& findMin( ) const;, it indicates that the function cannot change or write to member variables of that class. These member variables, also called state variables, include items like root in the BinaryTree class or item in the node class. This constraint is important for functions that are supposed to read and return member variables without modification, like a getName method that returns a customer's name. The const keyword helps the compiler catch unintentional mistakes at compile time or runtime, enforcing discipline in programming.

When const appears at the beginning of the return type, as in const EType& findMin( ) const;, it returns a const reference to a member variable. Returning by reference avoids creating a copy of the object, which is important for large objects. However, a function should never return a reference to a local variable, as local variables are destroyed when the function ends. The const at the start ensures that the calling function cannot change the member variable value through this reference, protecting the object's integrity while still providing efficient access. The caller should use set methods if changes are needed.

💡 Why this matters: Using const with references prevents expensive object copying while ensuring data integrity, making code both efficient and safe from unintended modifications.

Degenerate Binary Search Tree

Consider a BST created from the values 14, 15, 4, 9, 7, 18, 3, 5, 16, 20, 17. The root is 14, with smaller numbers in the left subtree and larger numbers in the right subtree, following the BST property. However, when data is provided in sorted order (3, 4, 5, 7, 9, 14, 15, 16, 17, 18, 20), the insert method creates a tree that looks like a linked list — each node has only a right child and no left child, forming a degenerate tree.

In this degenerate tree, searching for the value 20 requires traversing from 3 → 4 → 5 → 7 → 9 → 14 → 15 → 16 → 17 → 18 → 20, which is similar to linear search in a linked list. This defeats the purpose of a BST, where with one lakh numbers, a balanced tree would find any number in only 20 steps using the logarithmic property. The BST technique's benefit is lost because the tree is not balanced — the left and right subtrees do not have equal or similar heights.

To achieve balanced BST benefits, we need to keep the tree balanced. The ideal would be a complete binary tree where both left and right subtrees have the same height, requiring (2^(d+1) – 1) data items for a tree of depth d. However, this is impractical since we often cannot control the data input order.

AVL Tree

An AVL tree (named after Adelson-Velskii and Landis) is identical to a BST with two additional constraints: the height of left and right subtrees may differ by at most 1, and the height of an empty tree is defined to be (−1). The height of a binary tree is the maximum level of its leaves (also called the depth), calculated as the longest path from root to leaf.

The balance of a node is defined as the height of its left subtree minus the height of its right subtree. In an AVL tree, every node must have a balance of -1, 0, or 1. For example, in an AVL tree with root 5, left subtree height is 3 and right subtree height is 2, giving a difference of 1. At node 2, left subtree height is 1 and right subtree height is 2, also a difference of 1. At node 8, left subtree height is 1 and right subtree has height 0 (empty), giving a difference of 1. This condition must be satisfied at every node, not just the root.

In contrast, a non-AVL tree might have a node where left subtree height is 3 and right subtree height is only 1, giving a difference of 2. This violates the AVL condition. The AVL tree's balance factor at each node (shown as -1, 0, or 1) provides the information needed to maintain balance during insertions and deletions, ensuring the tree never degenerates into a linked list.

📌 Example: In the AVL tree with root 5, if the root's balance is -1, this means the right subtree's height is one greater than the left subtree's height. In the left subtree, a node with balance 1 indicates the left subtree's height is one greater than the right subtree's height. Nodes with balance 0 have equal left and right subtree heights.

⭐ Key Takeaways

The most critical things to remember from this lecture: The const keyword serves three distinct purposes in C++ — preventing parameter modification via const reference, preventing member variable modification in const member functions (const at end of signature), and protecting returned references from being used to modify member variables (const at start of return type). Degenerate BSTs (resembling linked lists) occur when data is inserted in sorted order, destroying the logarithmic search performance that makes BSTs valuable. AVL trees solve this by enforcing a balance condition where the height difference between left and right subtrees at any node cannot exceed 1. The balance of a node is calculated as (height of left subtree - height of right subtree), and must always be -1, 0, or 1 for an AVL tree.

🧠 Quick Revision Questions

1. What are the three different ways the const keyword is used in C++ function signatures, and what does each one protect?
2. Why does inserting sorted data into a BST create a degenerate tree, and what is the search time complexity in such a tree?
3. What is the definition of the balance of a node in a binary tree, and what values are allowed for a node in an AVL tree?
4. A node in a tree has a left subtree of height 3 and a right subtree of height 1. Is this node AVL balanced? Why or why not?
5. Why is requiring every node to have left and right subtrees of equal height (complete binary tree condition) impractical for real-world BST implementations?

📘 Lecture 20 — AVL Tree

📖 Overview: This lecture introduces the AVL tree, a self-balancing binary search tree named after its inventors Adelson-Velskii and Landis. It explains the concepts of height and balance, and details how to insert nodes while maintaining the tree's balance through rotations. Understanding AVL trees is crucial for ensuring efficient search operations in dynamic data structures.

🗂️ Topics Covered

The lecture covers the definition and properties of AVL trees, including the balance factor and height calculations. It then explains the conditions under which a tree becomes unbalanced after insertion, and introduces the rotation technique to restore balance. A step-by-step example of building an AVL tree by inserting numbers 1, 2, and 3 is provided, demonstrating the rotation process.

📝 Lecture Summary

AVL Tree

In 1962, Russian scientists Adelson-Velskii and Landis proposed criteria to prevent a binary search tree from becoming degenerate, developing the AVL tree (an acronym of their names). An AVL tree is identical to a BST, with one key difference: the height of the left and right subtrees can differ by at most 1. The height of an empty tree is defined as (–1). The balance (also called balance factor) of a node is the difference between the height of its left subtree and the height of its right subtree. In an AVL tree, the balance of any node must be 1, 0, or –1, depending on whether the left subtree is taller, equal, or shorter than the right subtree.

🔑 Definition — AVL Tree: A binary search tree where, for every node, the height of the left and right subtrees differ by at most 1. 📐 Formula: Balance = Height of Left Subtree – Height of Right Subtree → A value of 1, 0, or -1 is acceptable. 📌 Example: In a tree with root node 5, if the deepest node in the left subtree (node 3) is at level 3, the height of the left subtree is 3. If the deepest node in the right subtree (node 7) is at level 2, the height of the right subtree is 2. The balance of node 5 is 3 – 2 = 1, which is acceptable. However, for a tree to be an AVL tree, every node must satisfy this condition.

Height

The height of a binary tree is the maximum level of its leaves. This is the same definition as the depth of a tree.

🔑 Definition — Height: The maximum level of any leaf node in a binary tree.

Balance

The balance of a node in a binary search tree is defined as the height of its left subtree minus the height of its right subtree. At a particular node, the difference in heights of its left and right subtrees gives the balance of the node.

🔑 Definition — Balance: The height of the left subtree minus the height of the right subtree for a given node.

Insertion of Node in an AVL Tree

When inserting a new node into an AVL tree, we must ensure that the tree remains balanced. The new node is always inserted as a leaf node. The tree becomes unbalanced only if the newly inserted node:

• Is a left descendant of a node that previously had a balance of 1.
• Or is a descendant of a node that previously had a balance of –1. The first condition occurs because a node with balance 1 has a left subtree 1 level deeper than its right subtree. Adding a node to this left subtree increases its height by 1, making the difference 2. Similarly, a node with balance –1 has a right subtree 1 level deeper. Adding a node to this right subtree makes the balance –2.

💡 Why this matters: When insertion violates the AVL condition, we must reorganize the tree to restore balance while maintaining the same inorder traversal order. This process is called rotation.

🔑 Definition — Rotation: A tree modification process that restores balance to a node after an insertion violates the AVL condition, while preserving the inorder traversal order of the data. 📌 Example: Consider a tree where node A has balance 1, node B is its left child with balance 0, and a new node is inserted into T1 (left subtree of B). After insertion, the balance of A becomes 2 and B becomes 1. To fix this, we make B the new root, A becomes the right child of B, and T2 (right subtree of B) becomes the left subtree of A. The inorder traversal remains T1 B T2 A T3 in both cases.

Example (AVL Tree Building)

Let's build an AVL tree by inserting numbers 1, 2, and 3, checking the balance after each insertion and applying rotations when necessary.

Step 1: Insert 1. The tree has one node (1). No balance issues.

Step 2: Insert 2. Since 2 > 1, it becomes the right child of 1. The tree has nodes 1 (root) and 2 (right child). No balance issues yet.

Step 3: Insert 3. Since 3 > 1 and 3 > 2, it becomes the right child of 2. The tree now has nodes 1 (root at level 0), 2 (level 1), and 3 (level 2). The left subtree of node 1 has height 0, and its right subtree has height 2 (deepest node 3 at level 2). The balance of node 1 is 0 – 2 = –2, violating the AVL condition. We apply a left rotation at nodes 1 and 2. Node 2 becomes the new root, node 1 becomes its left child, and node 3 remains its right child. After rotation, the tree is balanced with all nodes having balance 0, and the inorder traversal is still 1 2 3.

📌 Example: Inserting 1, 2, 3 into an AVL tree. Before rotation: root 1 (balance -2), right child 2, right child 3. After left rotation: root 2 (balance 0), left child 1 (balance 0), right child 3 (balance 0).

⭐ Key Takeaways

An AVL tree maintains balance by ensuring the height difference between left and right subtrees of any node is at most 1, with balance factors of 1, 0, or -1. When an insertion violates this rule, rotation is applied to reorganize the tree and restore balance while preserving the inorder traversal order. The tree becomes unbalanced only when a new node is inserted as a descendant of a node with a balance factor of 1 (left subtree) or -1 (right subtree). The rotation process can be demonstrated with a simple example like inserting 1, 2, and 3, where a left rotation fixes the imbalance at node 1. The critical point is that different tree structures can produce the same sorted inorder traversal, allowing flexible rearrangement during balancing.

🧠 Quick Revision Questions

1. What is the maximum allowed difference between the heights of the left and right subtrees of any node in an AVL tree?
2. How is the balance factor of a node calculated?
3. Under what specific conditions does an AVL tree become unbalanced after inserting a new node?
4. What operation is used to restore balance in an AVL tree after an insertion violates the condition, and what key property of the tree must be preserved?
5. In the example of inserting numbers 1, 2, and 3, what was the balance factor of node 1 before rotation, and what rotation was applied to fix it?

📘 Lecture 21 — AVL Tree Building Example & Cases for Rotation

📖 Overview: This lecture continues building an AVL tree through example, demonstrating how nodes are inserted and rotated to maintain balance. It introduces the four cases of rotation violations and explains why single rotation works for some cases (left-left and right-right) but fails for others (left-right and right-left), setting up the need for double rotation.

🗂️ Topics Covered

The lecture covers a step-by-step AVL tree building example with nodes 3 through 16, calculating balance factors after each insertion and performing rotations when violations occur. It then formally categorizes the four cases of rotation violations and demonstrates with diagrams why single rotation fixes cases 1 and 4 (outside insertions) but not cases 2 and 3 (inside insertions).

📝 Lecture Summary

AVL Tree Building Example

This lecture continues building an AVL tree from the previous lecture, starting after inserting node 3. The tree after inserting 3 with a single left rotation has node 2 as the root, with node 1 as its left child and node 3 as its right child.

Inserting node 4: Compare with root node 2 — since 4 > 2, go right to node 3, then 4 > 3, so 4 becomes right child of 3. After insertion, check balance factors: node 4 has balance factor 0, node 3 has balance factor –1 (no left child, right subtree exists), node 1 has 0, and node 2 has balance factor 1 – 2 = –1. All nodes have balance factors within {0, 1, –1}, so the tree remains AVL.

🔑 Definition — Balance Factor: The height of the left subtree minus the height of the right subtree. For an AVL tree, every node's balance factor must be 0, 1, or –1.

Inserting node 5: The new node 5 becomes right child of node 4. Balance factors: node 5 = 0, node 4 = –1, node 3 = –2. Since node 3 has balance factor –2, a rotation is required. After a single left rotation on node 3, node 4 becomes the right child of node 2, and node 3 becomes the left child of node 4. All nodes now have balance factors of 0 or –1.

📐 Key observation — Inorder Traversal Preserved: Before rotation, inorder traversal of the tree in Fig 21.4 gives: 1 2 3 4 5. After rotation, the inorder traversal of Fig 21.5 also gives: 1 2 3 4 5. The rotation operation preserves the inorder traversal of the tree.

Inserting node 6: Node 6 becomes right child of node 5. Balance factors: node 6 = 0, node 5 = –1, node 3 = 0, node 4 = –1, node 1 = 0, node 2 = –2 (left subtree height 1, right subtree height 3). Root node 2 requires rotation. After rotation, node 4 becomes the new root, node 2 becomes left child of node 4, node 3 (formerly left child of node 4) becomes right child of node 2. Inorder traversal: 1 2 3 4 5 6.

💡 Why this matters: In a BST, the root node remains the same (the first inserted node). In an AVL tree, the root node keeps changing through rotations to maintain balance. This balancing ensures search efficiency — in an AVL tree built of n items, you can search up to 1.44 log₂ n levels maximum, compared to a linked list BST where you might traverse n–1 links.

Inserting node 7: Node 7 becomes right child of node 6. Balance factors: node 7 = 0, node 6 = –1, node 5 = –2. After rotation on node 5, node 5 becomes left child of node 6. The resulting tree is a perfect balanced binary tree — all nodes (7, 5, 3, 1, 6, 2, 4) have balance factor 0. Inorder traversal: 1 2 3 4 5 6 7.

Inserting node 16: Node 16 becomes right child of node 7. Balance factors for all nodes (16, 7, 5, 3, 1, 6, 2, 4) are 0 or –1. The tree remains AVL.

Inserting node 15: Node 15 becomes left child of node 16. Balance factors: node 5 = 0, node 16 = 1 (within limits), but node 7 = –2 (violation). A single left rotation on node 7 makes node 7 the left child of node 16, and node 15 becomes right child of node 7. However, after this rotation, balance factors are: node 15 = 0, node 7 = –1, node 16 = 2. The single rotation did not fix the imbalance — node 16 still has balance factor 2, which is outside AVL limits.

Cases for Rotation

When a node α requires rebalancing (balance factor ±2), since any node has at most two children and the height imbalance requires α's two subtrees to differ by 2 (or –2), the violation occurs in four cases:

1. An insertion into left subtree of the left child of α (left-left case)
2. An insertion into right subtree of the left child of α (left-right case)
3. An insertion into left subtree of the right child of α (right-left case)
4. An insertion into right subtree of the right child of α (right-right case)

The insertion occurs on the outside in cases 1 and 4 (left-left or right-right). Single rotation can fix the balance in cases 1 and 4.

The insertion occurs on the inside in cases 2 and 3 (left-right or right-left). A single rotation cannot fix these cases.

Case 1 (Single Right Rotation): Node k₂ is the root (α), k₁ is its left child, Z is its right child. X and Y are left and right subtrees of k₁. A new node is inserted as a child of X (outside insertion). A single right rotation makes k₁ the new root, k₂ becomes the right child of k₁, and Y becomes the left child of k₂. Inorder traversal: X k₁ Y k₂ Z (preserved).

Case 4 (Single Left Rotation): A new node is inserted as a child of Z (right subtree of the right child of the root α). A single left rotation on node k₁ makes k₁ rotate left. Node Y becomes the right child of node k₁.

Case 2 (Single Right Rotation Fails): A new node is inserted below node Y (inside insertion — right subtree of left child). After insertion, balance factor for node k₂ becomes 2. A single right rotation on k₂ produces balance factor for k₁ of –2. The tree remains unbalanced because the node Y subtree is unchanged — it changes its parent node but its subtree remains intact.

📐 Formula — Maximum Height of AVL Tree: 1.44 log₂ n, where n is the number of nodes in the tree. This guarantees efficient search operations.

⭐ Key Takeaways

The most critical concepts from this lecture are that AVL trees maintain balance through rotations performed immediately after insertions when any node's balance factor reaches ±2. Single rotations (left or right) successfully fix violations from outside insertions (left-left and right-right cases), but fail for inside insertions (left-right and right-left cases) because the problematic subtree (Y in case 2, or its mirror in case 3) remains unchanged through single rotation. The inorder traversal of the tree is always preserved during rotations, ensuring the binary search tree property is maintained. In an AVL tree, the root changes dynamically through rotations, achieving a maximum search depth of 1.44 log₂ n, which is significantly better than the worst-case linked list structure of a simple BST.

🧠 Quick Revision Questions

1. What are the four cases of rotation violations in an AVL tree, and which two can be fixed by a single rotation?
2. After inserting node 6 into the AVL tree, why was node 2 (the root) rotated instead of node 3 or node 4?
3. In the example of inserting node 15 (Fig 21.11 to Fig 21.12), why did the single left rotation on node 7 fail to restore balance?
4. What happens to the inorder traversal sequence when a rotation is performed on an AVL tree?
5. What is the maximum number of levels (links) you need to traverse to search for a node in an AVL tree built of n items?

📘 Lecture 22 — Cases of Rotations and Double Rotations in AVL Trees

📖 Overview: This lecture addresses situations where single rotations fail to restore balance in an AVL tree, specifically when the new node is inserted in the "inside" subtrees. It introduces the left-right and right-left double rotations to fix these cases and presents the complete C++ code for the avlInsert method, including balance checks and rotation logic.

🗂️ Topics Covered

The lecture begins by reviewing the four insertion scenarios where single rotation fails for inside insertions (cases 2 and 3). It then analyzes the problematic case 2, expands nodes to understand the structure, and introduces the left-right double rotation by performing two single rotations. The symmetric case 3 (right-left double rotation) is similarly addressed. Finally, the lecture presents the complete C++ code for the avlInsert method, including height calculations, balance factor checks, and conditional calls to single or double rotation routines while preserving inorder traversal.

📝 Lecture Summary

Cases of rotations

The lecture revisits the four insertion scenarios relative to the α node. In case-1 (new node in left subtree of α's left child) and case-4 (new node in right subtree of α's right child), single rotation restores balance. However, in case-2 (new node in right subtree of α's left child) and case-3 (new node in left subtree of α's right child), single rotation fails. The figure shows an α node k2 with left child k1 (with children X and Y) and right child Z. The new node is inserted under Y. After applying single right rotation, the tree remains unbalanced because the difference between left and right subtree levels at the new root k1 is still 2.

Left-right double rotation to fix case 2

To solve case 2, the lecture expands the Y subtree to show its root k2 and subtrees B and C. The tree now has three nodes (k1, k2, k3) and four subtrees (A, B, C, D). The new node is inserted either in B or C, making one of these subtrees two levels deeper than D. The inorder traversal of the original tree is A, k1, B, k2, C, k3, D. Since single rotation (making k1 or k3 the root) fails, the solution is to make k2 the new root. This is achieved through a double rotation: first, perform a left rotation between k1 and k2. This makes k2 the left child of k3, and subtree B becomes the right child of k1. Second, perform a right rotation between k2 and k3. This makes k2 the root, k1 its left child, and k3 its right child. The final inorder traversal is A, k1, B, k2, C, k3, D, preserving the original order and restoring balance.

Right-left double rotation to fix case 3

Case 3 is symmetric: the new node is inserted in the left subtree of the right child. Here, k1 is the root, k3 is its right child, and k2 is the inner child. The new node is inserted in k2's left (B) or right (C) subtree. To make k2 the root, first perform a right rotation between k2 and k3, bringing k2 up and making k3 its right child while subtree B stays with k2 and C attaches to k3. Then perform a left rotation between k1 and k2, making k2 the root with k1 as left child and k3 as right child. The inorder traversal is preserved.

The lecture revisits the example tree containing numbers 1 through 7 and 16. When inserting 15 as the left child of 16, it creates a case requiring right-left double rotation. After right rotation on the link of 15 and 16 (promoting 15 up and 16 down), then left rotation on the link of 7 and 15, the tree becomes balanced with 15 as root of the subtree and 7 and 16 as left and right children. The AVL condition is fulfilled: at node 4, left depth is 2 and right depth is 3 (difference = 1); at node 6, left depth is 1 and right depth is 2 (difference = 1). The resulting tree is balanced, and the height becomes 1.44 log₂ n in the worst case, ensuring logarithmic search time.

💡 Why this matters: The balanced nature of the AVL tree prevents the degenerate linked-list structure that occurs with sorted data, keeping search operations efficient at approximately log₂(10 million) levels even with ten million nodes.

The lecture continues inserting 14, which becomes the right child of 7 — an inner subtree of 15. This again requires double rotation (right-left). After right rotation between 14 and 15, then left rotation between 7 and 15, the tree balances with 7 as root, 4 and 15 as its left and right children. Inorder traversal (1, 2, 3, 4, 5, 6, 7, 14, 15, 16) remains sorted.

Inserting 13 requires only a single left rotation. The final tree has root 7, with left subtree containing 4, 2, 1, 3, 6, 5 and right subtree containing 15, 14, 13, 16. The tree remains balanced throughout the insertion process — it is not just balanced at the end, but at every step, the difference in levels between any node's right and left subtrees never exceeds 1.

C++ Code for avlInsert method

The lecture presents the complete C++ code for the avlInsert function, which incorporates balancing during insertion.

Function signature:

TreeNode<int>* avlInsert(TreeNode<int>* root, int info)

Logic:

1. If info < root->getInfo(), insert into left subtree via recursive call: root->setLeft(avlInsert(root->getLeft(), info)). After insertion, calculate height difference: int htdiff = height(root->getLeft()) - height(root->getRight()). If htdiff == 2, check whether the info is inserted in the outside subtree (info < root->left->info → single right rotation) or inside subtree (else → double left-right rotation).

2. If info > root->getInfo(), insert into right subtree similarly. Calculate: int htdiff = height(root->getRight()) - height(root->getLeft()). If htdiff == 2, check if info > root->right->info (outside, case 4 → single left rotation) or else (inside, case 3 → double right-left rotation).

3. If info == root->getInfo(), the value already exists. After all cases, update height: int ht = Max(height(root->getLeft()), height(root->getRight())); root->setHeight(ht + 1); return root.

The function returns the root (which may change due to rotations). The rotation routines (singleRightRotation, singleLeftRotation, doubleLeftRightRotation, doubleRightLeftRotation) are not shown in code but are described conceptually.

⭐ Key Takeaways

The most critical concepts from this lecture are: (1) Single rotations fix only "outside" insertions (left-left and right-right cases), while double rotations (two single rotations in sequence) are required for "inside" insertions (left-right and right-left cases). (2) The double rotation for case 2 (left-right) involves a left rotation between the lower node and middle node, followed by a right rotation between the middle node and α node, making the formerly middle node the new root. (3) The double rotation for case 3 (right-left) is symmetric, involving a right rotation first then a left rotation. (4) The avlInsert method recursively inserts a node, calculates the balance factor at each node, and performs the appropriate single or double rotation only at the node where the balance factor becomes 2, preserving inorder traversal and AVL balance. (5) The height of an AVL tree is at most 1.44 log₂ n, guaranteeing logarithmic search time regardless of insertion order.

🧠 Quick Revision Questions

1. In case 2 of AVL insertion (new node in right subtree of α's left child), why does single rotation fail, and how does a left-right double rotation solve the problem?
2. What are the two single rotations performed in a right-left double rotation (case 3), and which nodes become the new root, left child, and right child after the rotation?
3. In the avlInsert code, how does the algorithm determine whether to perform a single rotation or a double rotation when the balance factor becomes 2?
4. What is the worst-case height of an AVL tree, and why does this make search operations efficient even with millions of nodes?
5. In the example tree with nodes 1 through 7 and 16, what rotation(s) were required when inserting node 14, and what was the final shape of the tree after all insertions?