Website: [Link]

app/
Data Structure
Arrays: Representation and operations
Array Concept: An Array is a Linear List which has a finite number of elements and all
elements must be of the same (homogeneous) data type. The elements are referenced using index
numbers and stored in sequential or consecutive memory locations.
Example Array:
Index: 0 1 2 3 4 5
Elements: 6 8 4 12 10 8
Number of elements = Upper Bound - Lower Bound + 1 = 5 - 0 + 1 = 6
Array Memory Representation: To calculate the address of the k-th element in memory:
LOC(LA[k]) = Base Address (LA) + w × (k – 1)
Where:
- LA: Base address
- w: size (in bytes) of each element
- k: index position
Array Operations
1. Traversing: Access each element one by one.
2. Sorting: Bubble Sort compares adjacent elements and swaps them if out of order.
Example: Initial array = 4 5 7 8 10 3 2
3. Inserting: Insert item at a given position k.
Syntax: Insert(item, k)
4. Deleting: Remove item and shift remaining elements.
5. Searching: Binary Search on sorted data.
- MID = (BEG + END) / 2
- Loop while: BEG <= END and arr[MID] != searchItem
- Fails if MID data is altered.
Multi-Dimensional Arrays:
Matrix Example:
2 4 5
7 8 10
11 12 16
Matrix Size: M × N (Rows × Columns)
Address Calculation:
Row Major Order:
LOC (A[j][k]) = Base(A) + w × ((j - 1) × N + (k - 1))

[Link] [Link]
 Website: [Link]
Column Major Order:
LOC(A[j][k]) = Base(A) + w × ((k - 1) × M + (j - 1))
Example:
Base = 1001, w = 4 bytes
LOC (A [2][2]) = 1001 + 4 × (3×1 + 1) = 1001 + 16 = 1017
Pointer Arrays and Record Structures
Pointer Arrays: A pointer array is an array whose elements are pointers. These pointers can
point to other arrays or dynamic memory blocks. This is especially useful when dealing with data
where the size of each group varies.
Example: Grouped Records
Suppose we have 3 groups of records (e.g., characters or values). For example:
Group 1 → [x, y, z, a, b]
Group 2 → [...]
Group 3 → [...]
The challenge is how to store these groups efficiently in memory.
Methods of Storage
1. 1D Array: We can store all the group elements consecutively in a single 1D array. While this
is simple, we must track the start and end index of each group explicitly.
2. 2D Array: Another method is to use a 2D array where each row represents a group. However,
this may lead to memory wastage if groups have different sizes.
For example, using a 3×12 array = 36 slots, but if only 22 are used, the memory loss is 14 slots.
3. Array of Pointers: The most efficient method is using an array of pointers to store the address
of the first element of each group. Along with that, we can use additional arrays to store the
number of elements in each group and availability status.
Example: Group | First Address | Number of Elements | Available
1 | 0 | 4 | Yes
2 | 5 | ... | Yes
3 | 10 | ... | Yes
Record Structures: A record is a collection of fields that may contain different data types. In C
or C++, we use 'struct' to define a record.
Example:
struct Student {
int id;
char name[50];
float gpa;};

[Link] [Link]
 Website: [Link]

This structure allows us to hold multiple related values of different types under a single name.
Sparse and Dense Matrices: Concept and Operations
1. Concept
Dense Matrix: A matrix where most of the elements are non-zero.
Example:
[[3, 5, 7],
[1, 2, 4],
[6, 9, 8]]
Sparse Matrix: A matrix where most of the elements are zero.
Example:
[[0, 0, 5, 0],
[0, 8, 0, 0],
[0, 0, 0, 0]]
2. Why Use Sparse Matrices?
Sparse matrices are memory efficient and faster for computation when dealing with large
matrices with many zeros. They are commonly used in graph theory, image processing, scientific
computing, and machine learning.
3. Storage Representation of Sparse Matrices
3.1 Normal 2D Array
Stores all elements including zeros. Wastes memory.
3.2 Triplet Form (COO Format)
Stores only non-zero elements along with their row and column indices.
Example: | Row | Col | Value |
|-------|--------|--------|
|0 |2 |5 |
|1 |1 |8 |
3.3 Compressed Sparse Row (CSR)
Uses three arrays:
1. Values: Non-zero values
2. Column Indices: Column index for each value
3. Row Pointer: Starting index in 'values' for each row
4. Basic Operations on Sparse Matrices

[Link] [Link]
 Website: [Link]
4.1 Addition: Add corresponding non-zero elements. Efficient with CSR format.
4.2 Transpose: Swap row and column indices. Reorder for efficiency.
4.3 Multiplication: Multiply only corresponding non-zero elements. CSR × CSC format is
efficient.
5. Advantages of Sparse Representation
Comparison:
Dense Matrix:
- High memory usage
- Fast direct indexing
- Suitable for small/full matrices
Sparse Matrix:
- Low memory usage
- Optimized matrix operations
- Suitable for large, mostly-zero matrices
6. When to Use Sparse Matrices?
Use sparse matrices when:
- More than 50% of elements are zero
- Working with large datasets
- Need memory and computational efficiency
Applications include graph algorithms, social network analysis, and scientific modeling.
Stacks and queues: Concept, structures and basic operations
A stack is a list of elements in which an element may be inserted or deleted only at one end,
called the top of the stack. This means, in particular, that elements are removed from a stack in
the reverse order of that in which they were inserted into the stack. Special terminology is used
for two basic operations associated with stacks: (a) "Push" is the term used to insert an element
into a stack. (b) "Pop" is the term used to delete an element from a stack.
Suppose the following 6 elements are pushed, in order, onto an empty stack: AAA, BBB, CCC,
DDD, EEE, FFF Figure 6.3 shows three ways of picturing such a stack. For notational
convenience, we will frequently designate the stack by writing: STACK: AAA, BBB, CCC,
DDD, EEE, FFF The implication is that the right-most element is the top element. We emphasize
that, regardless of the way a stack is described, its underlying property is that insertions and
deletions can occur only at the top of the stack. This means EEE cannot be deleted before FFF is
deleted, DDD cannot be deleted before EEE and FFF are deleted, and reverse so on.
Consequently, the elements may be popped from the stack only in the order of that in which they
were pushed onto the stack.

[Link] [Link]
 Website: [Link]

Consider again the AVAIL list of available nodes discussed in Chapter 5. Recall that free nodes
were removed only from the beginning of the AVAIL list, and that new available nodes were
inserted only at the beginning of the AVAIL list. In other words, the AVAIL list was
implemented as a stack. This implementation of the AVAIL list as a stack is only a matter of
convenience rather than an inherent part of the structure. In the following subsection we discuss
an important situation where the stack is an essential tool of the processing algorithm itself.
6.3 ARRAY REPRESENTATION OF STACKS
Stacks may be represented in the computer in various ways, usually by means of a one-way list
or a linear array. Unless otherwise stated or implied, each of our stacks will be maintained by a
linear array STACK; a pointer variable TOP, which contains the location of the top element of
the stack; and a variable MAXSTK which gives the maximum number of elements that can be
held by the stack. The condition TOP = 0 or TOP = NULL will indicate that the stack is empty.
Figure 6.5 pictures such an array representation of a stack. (For notational convenience, the array
is drawn horizontally rather than vertically.) Since TOP = 3, the stack has three elements, XXX,
YYY and ZZZ; and since MAXSTK = 8, there is room for 5 more items in the stack.

[Link] [Link]
 Website: [Link]
The operation of adding (pushing) an item onto a stack and the operation of removing (popping)
an item from a stack may be implemented, respectively, by the following procedures, called
PUSH and POP. In executing the procedure PUSH, one must first test whether there is room in
the stack for the the procedure new item; if not, then we have the condition known as overflow.
Analogously, in executing POP, one must first test whether there is an element in the stack to be
deleted; if not, then we have the condition known as underflow.
Example 6.2 (a) Consider the stack in Fig. 6.5. We simulate the operation PUSH(STACK,
WWW):
1. Since TOP = 3, control is transferred to Step 2.
2. TOP = 3 + 1 = 4.
3. STACK[TOP] = STACK[4] = WWW.
4. Return.
Note that WWW is now the top element in the stack.
(b) Consider again the stack in Fig. 6.5. This time we simulate the operation POP(STACK,
ITEM):
1. Since TOP = 3, control is transferred to Step 2.
2. ITEM = ZZZ.
3. TOP = 3 - 1 = 2.
4. Return.
Observe that STACK[TOP] = STACK[2] = YYY is now the top element in the stack.
Minimizing Overflow: There is an essential difference between underflow and overflow in
dealing with stacks. Underflow depends exclusively upon the given algorithm and the given
input data, and hence there is no direct control by the programmer. Overflow, on the other hand,
depends upon the arbitrary choice of the programmer for the amount of memory space reserved
for each stack, and this choice does influence the number of times overflow may occur.
Example 6.3 Suppose a given algorithm requires two stacks, A and B. One can define an array
STACKA with n₁ elements for stack A and an array STACKB with n₂ elements for stack B.
Overflow will occur when either stack A contains more than n elements or stack contains more
than n₂ elements. B Suppose instead that we define a single array STACK with n = n₁+ n2
elements for stacks A and B together. As pictured in Fig. 6.6, we define STACK[1] as the
bottom of stack A and let A "grow" to the right, and we define STACK[n] as the bottom of stack
B and let B "grow" to the left. In this case, overflow will occur only when A and B together have
more than n = n₁+ n₂ elements. This technique will usually decrease the number of times
overflow occurs even though we have not increased the total amount of space reserved for the

[Link] [Link]
 Website: [Link]
two stacks. In using this data structure, the operations of PUSH and POP will need to be
modified.

6.4 LINKED REPRESENTATION OF STACKS

In this section we discuss the representation of stacks using a one-way list or singly linked list.
The advantages of linked lists over arrays have already been underlined. It is in this perspective
that one appreciates the use of a linked list for stacks in comparison to that of arrays. The linked
representation of a stack, commonly termed linked stack is a stack that is implemented using a
singly linked list. The INFO fields of the nodes hold the elements of the stack and the LINK
fields hold pointers to the neighboring element in the stack. The START pointer of the linked list
behaves as the TOP pointer variable of the stack and the null pointer of the last node in the list
signals the bottom of stack. Figure 6.7 illustrates the linked representation of the stack STACK
shown in Fig. 6.5.

A push operation into STACK is accomplished by inserting a node into the front or start of the
list and a pop operation is undertaken by deleting the node pointed to by the START pointer.
Figure 6.8 and Fig. 6.9 illustrate the push and pop operation on the linked stack STACK shown
in Fig. 6.7.

[Link] [Link]
 Website: [Link]

The array representation of stack calls for the maintenance of a variable MAXSTK which gives
the maximum number of elements that can be held by the stack. Also, it calls for the checking of
OVERFLOW in the case of push operation (TOP=MAXSTK) and UNDERFLOW in the case of
pop operation (TOP=0). In contrast, the linked representation of stacks is free of these
requirements. There is no limitation on the capacity of the linked stack and hence it can support
as many push operations (insertion of nodes) as the free-storage list ( the AVAIL list) can
support. This dispenses with the need to maintain the MAXSTK variable and consequently on
the checking of OVERFLOw of the linked stack during a push operation.
Example 6.4 Consider execution the of linked the following stack shown in Fig. 6.7, the
snapshots of the stack structure on operations are shown in Fig. 6.10:

[Link] [Link]
 Website: [Link]
6.10 QUEUES
A queue is a linear list of elements in which deletions can take place only at one end, called the
front, and insertions can take place only at the other end, called the rear. The terms "front" and
"rear" are used in describing a linear list'only when it is implemented as a queue.
Queues are also called first-in first-out (FIFO) lists, since the first element in a queue will be the
first element out of the queue. In other words, the order in which elements enter a queue is the
order in which they leave. This contrasts with stacks, which are last-in first-out (LIFO) lists.
Queues abound in everyday life. The automobiles waiting to pass through an intersection form a
queue, in which the first car in line is the first car through; the people waiting in line at a bank
form a queue, where the first person in line is the first person to be waited on; and so on. An
important example of a queue in computer science occurs in a timesharing system, in which
programs with the same priority form a queue while waiting to be executed. (Another structure,
called a priority queue, is discussed in Sec. 6.13.)
Example 6.10 Figure 6.19(a) is a schematic diagram of a queue with 4 elements; where AAA is
the front element and DDD is the rear element. Observe that the front and rear elements of the
queue are also, respectively, the first and last elements of the list. Suppose an element is deleted
from the queue. Then it must be AAA. This yields the queue in Fig. 6.19(b), queue where BBB
is now the front element. Next, suppose EEE is added to the the and then FFF is added to the
queue. Then they must be added at the rear of queue, as pictured in Fig. 6.19(c). Note that FFF is
now the rear element. Now suppose queue in another Fig. element is deleted from the queue;
then it must be BBB, to yield the deleted before 6.19(d). And so on. Observe that in such a data
structure, EEE will be will have to wait FFF until because it has been placed in the queue before
FFF. However, EEЕ CCC and DDD are deleted.

Representation of Queues: Queues may be represented in the computer in various ways,

usually by means at one-way lists or linear arrays. Unless otherwise stated or implied, each of
our queues will be maintained by a linear array QUEUE and two pointer variables: FRONT,
containing the location of the front element of the queue; and REAR, containing the location of
the rear element of the queue. The condition FRONT = NULL will indicate that the queue is

[Link] [Link]
 Website: [Link]
empty. Figure 6.20 shows the way the array in Fig. 6.19 will be stared in memory using an array
QUEUE with N elements. Figure 6.20 also indicates the way elements will be deleted from the
queue and the way new elements will be added to the queue. Observe that whenever an element
is deleted from the queue, the value of FRONT is increased by 1; this can be implemented by the
assignment FRONT := FRONT + 1 Similarly, whenever an element is added to the queue, the
value of REAR is increased by 1; this can be implemented by the assignment REAR := REAR +
1 This means that after N insertions, the rear element of the queue will occupy QUEUE[N] or, in
other words; eventually the queue will occupy the last part of the array. This occurs even though
the queue itself may not contain many elements. Suppose we want to insert an element ITEM
into a queue at the time the queue does occupy the last part of the array, i.e., when REAR = N.
One way to do this is to simply move the entire queue to the beginning of the array, changing
FRONT and REAR accordingly, and then inserting ITЕM as above. This procedure may be very
expensive. The procedure we adopt is to assume that the array QUEUE is circular, that is, that
QUEUE[1] comes after QUEUE[N] in the array. With this assumption, we insert ITEM into the
queue by assigning ITEM to QUEUE[1]. Specifically, instead of increasing REAR to N + 1, we
reset REAR = 1 and then assign QUEUE[REAR] := ITЕM

Similarly, if FRONT = N and an element of QUEUE is deleted, we reset FRONT = 1 instead of

increasing FRONT to N + 1. (Some readers may recognize this as modular arithmetic, discussed
in Sec. 2.2.)
Suppose that our queue contains only one element, i.e., suppose that
FRONT = REAR ≠ NULL
and suppose that the element is deleted. Then we assign
FRONT := NULL and REAR := NULL

[Link] [Link]
 Website: [Link]
to indicate that the queue is empty.
Example 6.11 Figure 6.21 shows how a queue may be maintained by a circular array QUEUE
with N locations = 5 memory locations. Observe that the queue always occupies consecutive
except when it occupies locations at the beginning and at the end of the array. If the queue is
viewed as a circular array, this means that it still occupies consecutive locations. Also, as
indicated by Fig. 6.21(m), the queue will be empty only when FRONT = REAR and an element
is deleted. For this reason, NULL is assigned to FRONT and REAR in Fig. 6.21(m).

We are now prepared to formally state our procedure QINSERT (Procedure 6.13), which inserts
a data ITEM into a queue. The first thing we do in the procedure is to test for overflow, that is, to
test whether or not the queue is filled. Next we give a procedure QDELETE (Procedure 6.14),
which deletes the first element from a queue, assigning it to the variable ITEM. The first thing
we do is to test for underflow, i.e., to test whether or not the queue is empty.
6.11 LINKED REPRESENTATION OF QUEUES
In this section we discuss the linked representation of a queue. A linked queue is a queue
implemented as a linked list with two pointer variables FRONT and REAR pointing to the nodes
which is in the FRONT and REAR of the queue. The INFO fields of the list hold the elements of

[Link] [Link]
 Website: [Link]
the queue and the LINK fields hold pointers to the neighboring elements in the queue. Fig. 6.22
illustrates the linked representation of the queue shown in Fig. 6.16(a).

In the case of insertion into a linked queue, a node borrowed from the AVAIL list and carrying
the item to be inserted is added as the last node of the linked list representing the queue. The
REAR pointer is updated to point to the last node just added to the list. In the case of deletion,
the first node of the list pointed to by FRONT is deleted and the FRONT pointer is updated to
point to the next node in the list. Fig. 6.23 and Fig. 6.24 illustrate the insert and delete operations
on the queue shown in Fig. 6.22.

Example 6.12 For the linked queue shown in Fig. 6.22, the snapshots of the queue structure after
the execution of the following operations are shown in Fig. 6.25. (i) Delete (ii) Delete (iii) Insert
FFF Original linked queue:

[Link] [Link]
 Website: [Link]
6.12 DEQUES A deque (pronounced either "deck" or "dequeue") is a linear list in which
elements can be added or removed at either end but not in the middle. The tern deque is a
contraction of the name double-ended queue. There are various ways of representing a deque in a
computer. Unless it is otherwise stated or implied, we will assume our deque is maintained by a
circular array DEQUE with pointers LEFT and RIGHT, which point to the two ends of the
deque. We assume that the elements extend from the left end to the right end in the array. The
term "circular" comes from the fact that we assume that DEQUE[1] comes after DEQUE[N] in
the array. Figure 6.26 pictures two deques, each with 4 elements maintained in an array with N =
8 memory locations. The condition LEFT = NULL will be used to indicate that a deque is empty.
There are two variations of a deque-namely, an input-restricted deque and an output-restricted
deque-which are intermediate between a deque and a queue. Specifically, an input-restricted
deque is a deque which allows insertions at only one end of the list but allows deletions at both
ends of the list; and an output-restricted deque is a deque which allows deletions at only one end
of the list but allows insertions at both [Link] the list.

The procedures which insert and delete elements in deques and the variations on those
procedures are given as supplementary problems. As with queues, a complication may arise (a)
when there is overflow, that is, when an element is to be inserted into a deque which is already
full, or (b) when there is undetflow, that is, when an element is to be deleted from a deque which
is empty. The procedures must consider these possibilities.
6.13 PRIORITY QUEUES A priority queue is a collection of elements such that cach element
has been assigned a priority and such that the order in which elements are deleted and processed
comes from the following rules:
(1) An element of higher priority is processed before any element of lower priority.
(2) Two elements with the same priority are processed according to the order in which they were
added to the queue.
A prototype of a priority queue is a timesharing system: programs of high priority are processed
first, and programs with the same priority form a standard queue. There are various ways of
maintaining a priority queue in memory. We discuss two of them here: one uses a one-way list,
and the other uses multiple queues. The ease or difficulty in adding elements to or deleting them
from a priority queue clearly depends on the representation that one chooses.

[Link] [Link]
 Website: [Link]
One-Way List Representation of a Priority Queue: One way to maintain a priority queue in
memory is by means of a one-way list, as follows:
(a) Each node in the list will contain three items of information: an information field INFO, a
priority number PRN and a link number LINK.
(b) A node X precedes a node Y in the list (1) when X has higher priority than Y or (2) when
both have the same priority but X was added to the list before Y. This means that the order in the
one-way list corresponds to the order of the priority queue.
Priority numbers will operate in the usual way: the lower the priority number, the higher the
priority.
Example 6.13 Figure 6.27 shows a schematic diagram of a priority queue with 7 elements. The
diagram does not tell us whether BBB was added to the list before or after DDD. On the other
hand, the diagram does tell us that BBB was inserted before CCC, because BBB and CCC have
the same priority number and BBB appears before CCC in the list. Figure 6.28 shows the way
the priority queue may appear in memory using linear arrays INFO, PRN and LINK. (See Sec.
5.2.)

The main property of the one-way list representation of a priority queue is that the element in the
queue that should be processed first always appears at the beginning of the one-way list.

[Link] [Link]
 Website: [Link]
Accordingly, it is a very simple matter to delete and process an element from our priority queue.
The outline of the algorithm follows.
Algorithm 6.17: This algorithm deletes and processes the first element in a priority queue which
appears in memory as a one-way list.
1. Set ITEM := INFO[START]. [This saves the data in the first node.]
2. Delete first node from the list.
3. Process ITEM.
4. Exit.
The details of the algorithm, including the possibility of underflow, are left as an exercise.
Adding an element to our priority queue is much more complicated than deleting an element
from the queue, because we need to find the correct place to insert the element. An outline of the
algorithm follows.
Algorithm 6.18: This algorithm adds an ITEM with priority number N to a priority queue which
is maintained in memory as a one-way list.
(a) Traverse the one-way list until finding a node X whose priority number exceeds N. Insert
ITEM in front of node X.
(b) If no such node is found, insert ITEM as the last element of the list.
The above insertion algorithm may be pictured as a weighted object "sinking" through layers of
elements until it meets an element with a heavier weight. The details of the above algorithm are
left as an exercise. The main difficulty in the algorithm comes from the fact that ITEM is
inserted before node X. This means that, while traversing the list, one must also keep track of the
address of the node preceding the node being accessed.
Example 6.14 Consider the priority queue in Fig. 6.27. Suppose an item XXX with priority
number 2 is to be inserted into the queue. We traverse the list, comparing priority numbers.
Observe that DDD is the first element in the list whose priority number exceeds that of XXX.
Hence XXX is inserted in the list in front of DDD, as pictured in Fig. 6.29. Observe that XXX
comes after BBB and CCC, which have the same priority as XXX. Suppose now that an element
is to be deleted from the queue. It will be AAA, the first element in the list. Assuming no other
insertions, the next element to be deleted will be BBB, then CCC, then XXX, and so on.

[Link] [Link]
 Website: [Link]
Array Representation of a Priority Queue: Another way to maintain a priority queue in
memory is to use a separate queue for each level of priority (or for each priority number). Each
such queue will appear in its own circular array and must have its own pair of pointers, FRONT
and REAR. In fact, if each queue is allocated the same amount indicates of space, a two-
dimensional array QUEUE can be used instead of the linear arrays. Figure 6.30 indicates this
representation for the priority queue in Fig. 6.29. Observe that FRONT[K] and REAR[K]
contain, respectively, the front and rear elements of row K of QUEUE, the row that maintains the
queue of elements with priority number K.

The following are outlines of algorithms for deleting and inserting elements in a priority queue
that is maintained in memory by a two-dimensional array QUEUE, as above. The details of the
algorithms are left as exercises.
Algorithm 6.19: This algorithm deletes and processes the first element in a priority queue
maintained by a two-dimensional array QUEUE.
1. [Find the first nonempty queue.] Find the smallest K such that FRONT[K] ≠ NULL.
2. Delete and process the front element in row K of QUEUE.
3. Exit.
Algorithm 6.20: This algorithm adds an ITEM with priority number M to a priority queue
maintained by a two-dimensional array QUEUE. Summary
1. Insert ITEM as the rear element in row M of QUEUE.
2. Exit.
Quick-sort and Polish notation: Applications of stack
Polish Notation: For most common arithmetic operations, the operator symbol is placed
between its two operands. For example,
A+B C-D E*F G/H
This is called infix notation. With this notation, we must distinguish between
(A + B)*C and A + (B*C)
by using either parentheses or some operator-precedence convention such as the usual
precedence levels discussed above. Accordingly, the order of the operators and operands in an

[Link] [Link]
 Website: [Link]
arithmetic expression does not uniquely determine the order in which the operations are to be
performed. Polish notation, named after the Polish mathematician Jan Lukasiewicz, refers to the
notation in which the operator symbol is placed before its two operands. For example, prefix
+AB -CD *EF /GH
We translate, step by step, the following infix expressions into Polish notation using brackets [ ]
to indicate a partial translation:
(A + B)* C = [+AB]*C = *+ AВС
A + (B*C) = A + [*BC) = + A*BC
(A + B)/(C - D) = [+AB]/[-CD] = / + AB - CD
The fundamental property of Polish notation is that the order in which the operations are to be
performed is completely determined by the positions of the operators and operands in the
expression. Accordingly, one never needs parentheses when writing expressions in Polish
notation. Reverse Polish notation refers to the analogous notation in which the operator symbol
is placed after its two operands: AB+ CD- EF* GH/
Again, one never needs parentheses to determine the order of the operations in any arithmetic
expression written in reverse Polish notation. This notation is frequently called postfix (or suffix)
notation, paragraph. whereas prefix notation is the term used for Polish notation, discussed in the
preceding paragraph.

[Link] [Link]
 Website: [Link]

[Link] [Link]
 Website: [Link]

6.6 QUICKSORT, AN APPLICATION OF STACKS

Let A be a list of n data items. "Sorting A" refers to the operation of rearranging the elements of
A so that they are in some logical order, such as numerically ordered when A contains numerical
data, or alphabetically ordered when A contains character data. The subject of sorting, including
various sorting algorithms, is treated mainly in Chapter 9. This section gives only one sorting
algorithm, called quicksort, in order to illustrate an application of stacks.
Quicksort is an algorithm of the divide-and-conquer type. That is, the problem of sorting a set is
reduced to the problem of sorting two smaller sets. We illustrate this "reduction step" by means
of a specific example.
Suppose A is, the following list of 12 numbers:
(44 )33, 11, 55, 77, 90, 40, 60, 99, 22, 88, (66)
The reduction step of the quicksort algorithm finds the final position of one of the numbers; in
this illustration, we use the first number, 44. This is accomplished as follows. Beginning with the
last number, 66, scan the list from right to left, comparing each number with 44 and stopping at
the first number less than 44. The number is 22. Interchange 44 and 22 to obtain the list
(22) 33, 11, 55, 77, 90, 40, 60, 99, (44) 88, 66
(Observe that the numbers 88 and 66 to the right of 44 are each greater than 44.) Beginning with
22, next scan the list in the opposite direction, from left to right, comparing each number with 44
obtain and stopping at the first number greater than 44. The number is 55. Interchange 44 and 55
to obtain the list.
22, 33, 11, (44) 77, 90. 40, 60, 99, (55) 88, 66

[Link] [Link]
 Website: [Link]
(Observe that the numbers 22, 33 and 11 to the left of 44 are each less than 44.) Beginning this
time with 55, now scan the list in the original direction, from right to left, until meeting the first
number less than 44. It is 40. Interchange 44 and 40 to obtain the list
22, 33, 11, (40) 77, 90, (44) 60, 99, 55, 88, 66
(Again, the numbers to the right of 44 are each greater than 44.) Beginning with 40, scan the list
from left to right. The first number greater than 44 is 77. Interchange 44 and 77 to obtain the list
22, 33, 11, (40) (44) 90, (77) 60, 99, 55, 88, 66
(Again, the numbers to the left of 44 are each less than 44.) Beginning with 77, scan the list from
right to left seeking a number less than 44. We do not meet such a number before meeting 44.
This means all numbers have been scanned and compared with 44. Furthermore, all numbers less
than 44 now form the sublist of numbers to the left of 44, and all numbers greater than 44 now
form the sublist of numbers to the right of 44, as shown below:
[22, 33, 11, 40] (44) [90, 77, 60, 99, 55, 88, 66]
First sublist Second sublist
Thus 44 is correctly placed in its final position, and the task of sorting the original list A has now
been reduced to the task of sorting each of the above sublists.
The above reduction step is repeated with each sublist containing 2 or more elements. Since we
can process only one sublist at a time, we must be able to keep track of some sublists for future
processing. This is accomplished by using two stacks, called LOWER and UPPER, to
temporarily "hold" such sublists. That is, the addresses of the first and last elements of each
sublist, called its boundary values, are pushed onto the stacks LOWER and UPPER, respectively;
and the reduction step is applied to a sublist only after its boundary values are removed from the
stacks. The following example illustrates the way the stacks LOWER and UPPER are used.

[Link] [Link]
 Website: [Link]

Recursion: Concept and applications

Recursion is an important concept in computer science. Many algorithms can be best described
in terms of recursion. This section introduces this powerful tool, and Sec. 6.9 will show how
recursion may be implemented by means of stacks.
Suppose P is a procedure containing either a Call statement to itself or a Call statement to a
second procedure that may eventually result in a Call statement back to the original procedure P.
Then P is called a recursive procedure. So that the program will not continue to run indefinitely,
a recursive procedure must have the following two properties:
(1) There must be certain criteria, called base criteria, for which the procedure does not call
itself.
(2) Each time the procedure does call itself (directly or indirectly), it must be closer to the base
criteria.
A recursive procedure with these two properties is said to be well-defined. 6.19 Similarly, a
function is said to be recursively defined if the function definition refers to itself. Again, in order
for the definition not to be circular, it must have the following two properties: (1) There must be
certain arguments, called base values, for which the function does not refer to itself. (2) Each
time the function does refer to itself, the argument of the function must be closer to a base value
A recursive function with these two properties is also said to be well-defined. The following
examples should help clarify these ideas.

[Link] [Link]
 Website: [Link]
Factorial Function: The product of the positive integers from 1 to n, inclusive, is called "n
factorial" and is usually denoted by n!:
n! = 12 3... (n 2)(n -1)n
It is also convenient to define 0! = 1, so that the function is defined for all nonnegative integers.
Thus we have
0! = 1 1! = 1 2! = 1.2 = 2 3! = 1.2.3 = 6 4! = [Link]=24 5! =[Link].5 = 120
6! =1 .[Link].6=720
and so on. Observe that
5! =5.4! = 5.24 = 120 and 6! = 6.5! = 6.120 = 720
This is true for every positive integer n; that is,
n! = n (n 1)!
Accordingly, the factorial function may also be defined as follows:
Definition 6.1: (Factorial Function) (a) If n = 0, then n! = 1. (b) If n > 0, then n! = n · (n – 1)!
Observe that this definition of n! is recursive, since it refers to itself when it uses (n - 1)!
However, (a) the value of n! is explicitly given when n = 0 (thus 0 is the base value); and (b) the
value of n! for arbitrary n is defined in terms of a smaller value of n which is closer to the base
value 0. Accordingly, the definition is not circular, or in other words, the procedure is well-
defined.
Example 6.9 Let us calculate 4! using the recursive definition. This calculation requires the
following nine steps:

[Link] [Link]
 Website: [Link]
Fibonacci Sequence: The celebrated Fibonacci sequence (usually denoted by F, F, F₂,...) is as
follows:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,
That is, Fo = 0 and F₁ = 1 and each succeeding tern is the sum of the two preceding terms. For
example, the next two terms of the sequence are
34 + 55 = 89 and 55 + 89 = 144
A formal definition of this function follows:
Definition 6.2: (Fibonacci Sequence)
(a) If n = 0 or n = 1, then F = n.
(b) If n > 1, then Fn= Fn-2 + Fn-1
This is another example of a recursive definition, since the definition refers to itself when it uses
Fn-2 and Fn-1 Here (a) the base values are 0 and 1, and (b) the value of Fn is defined in terms of
smaller values of n which are closer to the base values. Accordingly, this function is well
defined.
A procedure for finding the nth term F of the Fibonacci sequence follows.
Procedure 6.10: FIBONACCI(FIB, N)
This procedure calculates FN and returns the value in the first parameter FIB.

This is another example of a recursive procedure, since the procedure contains a call to itself. In
fact, this procedure contains two calls to itself. We note (see Solved Problem 6.17) that one can
also write an iterative procedure to calculate Fn which does not use recursion.
Divide-and-Conquer Algorithms
Data Structures Consider a problem P associated with a set S. Suppose A is an algorithm which
partitions S into smaller sets such that the solution of the problem P for S is reduced to the
solution of P for one or more of the smaller sets. Then A is called a divide-and-conquer
algorithm.
Two examples of divide-and-conquer algorithms, previously treated, are the quicksort algorithm
Sec. 6.6 and the binary search algorithm in Sec. 4.7. Recall that the quicksort algorithm uses
reduction step to find the location of a single element and to reduce the problem of sorting the
entire set to the problem of sorting smaller sets. The binary search algorithm divides the given

[Link] [Link]
 Website: [Link]
sorted set into two halves so that the problem of searching for an item in the entire set is reduced
to the problem of searching for the item in one of the two halves.
A divide-and-conquer algorithm A may be viewed as a recursive procedure. The reason for this
is that the algorithm A may be viewed as calling itself when it is applied to the smaller sets. The
base criteria for these algorithms are usually the one-element sets. For example, with a sorting
algorithm, a one-element set is automatically sorted; and with a searching algorithm, a one-
element set requires only a single comparison.
Ackermann Function
The Ackermann function is a function with two arguments each of which can be assigned any
nonnegative integer: 0, 1, 2,.... This function is defined as follows:
Definition 6.3: (Ackermann Function)
(a) If m = 0, then A(m, n) = n+ 1.
(b) If m ≠ 0 but n = 0, then A(m, n) = A(m - 1, 1).
(c) If m ≠ 0 and n ≠ 0, then A(m, n) = A(m - 1, A(m, n - 1))
Once more, we have a recursive definition, since the definition refers to itself in parts (b) and (c).
Observe that A(m, n) is explicitly given only when m = 0. The base criteria are the pairs
(0, 0), (0, 1), (0, 2), (0, 3), ..., (0, n),...
Although it is not obvious from the definition, the value of any A(m, n) may eventually be
expressed in terms of the value of the function on one or more of the base pairs.
The value of A(1, 3) is calculated in Solved Problem 6.18. Even this simple case requires 15
steps. Generally speaking, the Ackermann function is too complex to evaluate on any but a
trivial example. Its importance comes from its use in mathematical logic. The function is stated
here mainly to give another example of a classical recursive function and to show that the
recursion part of a definition may be complicated.
6.8 TOWERS OF HANOI
The preceding section gave examples of some recursive definitions and procedures. This section
shows how recursion may be used as a tool in developing an algorithm to solve a particular
problem. The problem we pick is known as the Towers of Hanoi problem.
Suppose three pegs, labeled A, B and C, are given, and suppose on peg A there are placed a
finite number n of disks with decreasing size. This is pictured in Fig. 6.14 for the case n = 6. The
object of the game is to move the disks from peg A to peg C using peg B as an auxiliary. The
rules of the game are as follows:

[Link] [Link]
 Website: [Link]
(a) Only one disk may be moved at a time. Specifically, only the top disk on any peg may be
moved to any other peg.
(b) At no time can a larger disk be placed on a smaller disk.

Sometimes we will write X → Y to denote the instruction "Move top disk from peg X to peg Y,”
where X and Y may be any of the three pegs.
The solution to the Towers of Hanoi problem for n = 3 appears in Fig. 6.15. Observe that it
consists of the following seven moves:
n = 3: Move top disk from peg A to peg C.
Move top disk from peg A to peg B.
Move top disk from peg C to peg B.
Move top disk from peg A to peg C.
Move top disk from peg B to peg A.
Move top disk from peg B to peg C.
Move top disk from peg A to peg C.

In other words,
n = 3: A → С, А → B, C → В, А → С. В → А, В → С, А→ С

[Link] [Link]
 Website: [Link]
For completeness, we also give the solution to the Towers of Hanoi problem for n = 1 and n = 2:
n= 1: A→C.
n =2: A→B,A→ C,B→ C
Note that n = 1 uses only one move and that n = 2 uses three moves.
Rather than finding a separate solution for each n, we use the technique of recursion to develop a
general solution. First we observe that the solution to the Towers of Hanoi problem for n > 1
disks may be reduced to the following subproblems:
(1) Move the top n -1 disks from peg A to peg B.
(2) Move the top disk from peg A to peg C: A → C.
(3) Move the top n - 1 disks from peg B to peg C.
This reduction is illustrated in Fig. 6.16 for n = 6. That is, first we move the top five disks from
peg A to peg B, then we move the large disk from peg A to peg C, and then we move the top five
disks from peg B to peg C.

Let us now introduce the general notation to

TOWER(N, BEG, AUX, END)
To denote a procedure which moves the top n disks from the initial peg BEG to the final peg
END using the peg AUX as an-auxiliary. When n = 1, we have the following obvious solution:
TOWER(1, BEG, AUX, END) consists of the single instruction BEG → END
Furthermore, as discussed above, when n > 1, the solution may be reduced to the solution of the
following three subproblems:
(1) TOWER(N - 1, BEG, END, AUX)
(2) TOWER(1, BEG, AUX, END) or BEG → END

[Link] [Link]
 Website: [Link]
(3) TOWER(N – 1, AUX, BEG, END)
Observe that each of these three subproblems may be solved directly or is essentially the same as
the original problem using fewer disks. Accordingly, this reduction process does yield a
recursive solution to the Towers of Hanoi problem. Figure 6.17 contains a schematic diagram of
the above recursive solution for:

Observe that the recursive solution for n = 4 disks consists of the following 15 moves:
A→B A→C B→C A→B C→А C→B А→B A→C B→C B→A С→А В→С
A→B A→C B→C
In general, this recursive solution requires f(n) = 2" - 1 moves for n disks. We summarize our
investigation with the following formally written procedure.
6.9 Implementation of Recursive Procedures by Stacks
The preceding sections showed how recursion may be a useful tool in developing algorithms for
specific problems. This section shows how stacks may be used to implement recursive
procedures.

[Link] [Link]
 Website: [Link]
It is instructive to first discuss subprograms in general.
Recall that a subprogram can contain both parameters and local variables. The parameters are the
variables which receive values from objects in the calling program, called arguments, and which
transmit values back to the calling program. Besides the parameters and local variables, the
subprogram must also keep track of the return address in the calling program. This return address
is essential since control must be transferred back to its proper place in the calling program. At
the time that the subprogram is finished executing and control is transferred back to the calling
program, the values of the local variables and the return address are no longer needed.
Suppose our subprogram is a recursive program. Then each level of execution of the subprogram
may contain different values for the parameters, local variables, and the return address.
Furthermore, if the recursive program does call itself, then these current values must be saved,
since they will be used again when the program is reactivated.
Suppose a programmer is using a high-level language that supports recursion, such as Pascal.
Then the computer handles the bookkeeping that keeps track of all the values of the parameters,
local variables, and return addresses. On the other hand, if a programmer is using a high-level
language that does not support recursion, such as FORTRAN, then the programmer must set up
the necessary bookkeeping by translating the recursive procedure into a non-recursive one. This
bookkeeping is discussed below.
Translation of a Recursive Procedure into a Nonrecursive Procedure
Suppose P is a recursive procedure. We assume that P is a subroutine subprogram rather than a
function subprogram. (This is no loss in generality, since function subprograms can easily be
written as subroutine subprograms.) We also assume that a recursive call to P comes only from
the procedure P. (The treatment of indirect recursion lies beyond the scope of this text.) The
translation of the recursive procedure P into a nonrecursive procedure works as follows. First of
all, one defines:
(1) A stack STPAR for each parameter PAR
(2) A stack STVAR for each local variable VAR
(3) A local variable ADD and a stack STADD to hold return addresses
Each time there is a recursive call to P, the current values of the parameters and local variables
are pushed onto the corresponding stacks for future processing, and each time there is a recursive
return to P, the values of parameters and local variables for the current execution of P are
restored from the stacks. The handling of the return addresses is more complicated; it is done as
follows. Suppose the procedure P contains a recursive Call P in Step K. Then there are two
return addresses associated with the execution of this Step K:
(1) There is the current return address of the procedure P, which will be used when the current
level of execution of P is finished executing.

[Link] [Link]
 Website: [Link]
(2) There is the new return address K + 1, which is the addres of the step following the Call P
and which will be used to return to the current level of execution of procedure P.
Some texts push the first of these two addresses, the current return address, onto the return
address stack STADD, whereas some texts push the second address, the new return address K +
1, onto STADD. We will choose the latter method, since the translation of P into a nonrecursive
procedure will then be simpler. This also means, in particular, that an empty stack STADD will
indicate a return to the main program that initially called the recursive procedure P. (The
alternative translation which pushes the current return address onto the stack is discussed in
Solved Problem 6.21.) The algorithm which translates the recursive procedure P into a
nonrecursive procedure follows. It consists of three parts: (1) preparation, (2) translating each
recursive Call P in procedure P and (3) translating each Return in procedure P.
(1) Preparation.
(a) Define a stack STPAR for each parameter PAR, a stack STVAR for each local
variable VAR, and a local variable ADD and a stack STADD to hold return addresses.
(b) Set TOP := NULL.
(2) Translation of "Step K. Call P."
(a) Push the current values of the parameters and local variables onto the appropriate
stacks, and push the new return address [Step] K + 1 onto STADD.
(b) Reset the parameters using the new argument values.
(c) Go to Step 1. [The beginning of the procedure P.]
(3) Translation of "Step J. Return."
(a) If STADD is empty, then: Return. [Control is returned to the main program.]
(b) Restore the top values of the stacks. That is, set the parameters and local variables
equal to the top values on the stacks, and set ADD equal to the top value on the stack STADD.
(c) Go to Step ADD.
Observe that the translation of "Step K. Call P" does depend on the value of K, but that the
translation of "Step J. Return" does not depend on the value of J. Accordingly, one need translate
only one Return statement, for example, by using Step L. Return. as above and then replace
every other Return statement by Go to Step L. This will simplify the translation of the procedure.

[Link] [Link]
 Website: [Link]
Linked lists: Representation and various operations
A linked list, or one-way list, is a linear collection of data elements, called nodes, where the
linear order is given by means of pointers. That is, each node is divided into two parts: the first
part contains the information of the element, and the second part, called the link field or
nextpointer field, contains the address of the next node in the list. Figure 5.2 is a schematic
diagram of a linked list with 6 nodes. Each node is pictured with two parts. The left part
represents the information part of the node, which may contain an entire record of data items
(e.g., NAME, ADDRESS....). The right part represents the nextpointer field of the node, and
there is an arrow drawn from it to the next node in the list. This follows the usual practice of
drawing an arrow from a field to a node when the address of the node appears in the given field.
The pointer of the last node contains a special value, called the null pointer, which is any invalid
address.

(In actual practice, 0 or a negative number is used for the null pointer.) The null pointer, denoted
by x in the diagram, signals the end of the list. The linked list also contains a list pointer
variable-called START or NAME-which contains the address of the first node in the list; hence
there is an arrow drawn from START to the first node. Clearly, we need only this address in
START to trace through the list. A special case is the list that has no nodes. Such a list is called
the null list or empty list and is denoted by the null pointer in the variable START.
REPRESENTATION OF LINKED LİSTS IN MEMORY: Let LIST be a linked list. Then
LIST will be maintained in memory, unless otherwise specified or implied, as follows. First of
all, LIST requires two linear arrays-we will call them here INFO and LINK—such that INFO[K]
and LINK[K] contain, respectively, the information part and the nextpointer field of a node of
LIST. As noted above, LIST also requires a variable name-such as START-which contains the
location of the beginning of the list, and a nextpointer sentinel - denoted by NULL-which
indicates the end of the list. Since the subscripts of the arrays INFO and LINK will usually be
positive, we will choose NULL = 0, unless otherwise stated.
The following examples of linked lists indicate that the nodes of a list need not occupy adj
elements in the arrays INFO and LINK, and that more than one list may be maintained in the
linear arrays INFO and Link.
Example 5.2 Figure 5.4 pictures a linked list in memory where each node of the list contains a
single character. We can obtain the actual list of characters, or, in other words, the string, ás
follows:

[Link] [Link]
 Website: [Link]
START = 9, so INFO [9] = N is the first character.
LINK [9] = 3, so INFO [3] = 0 is the second character.
LINK [3] = 6, so INFO [6] = (blank) is the third character.
LINK [6] = 11, so INFO [11] = E is the fourth character.
LINK [11] = 7, so INFO [7] = X is the fifth character.
LINK [7] = 10, so INFO [10] = I is the sixth character.
LINK [10] = 4, so INFO [4] = T is the seventh character.
LINK [4] = 0, the NULL value, so the list has ended. In other words, NO EXIT is the character
string.

Example 5.5 Suppose the personnel file of a small company contains the following data on its
nine employees:
Name, Social Security Number, Sex, Monthly Salary
Normally, four parallel arrays, say NAME, SSN, SEX, SALARY, are required to store the data
as discussed in Sec. 4.12. Figure 5.7 shows how the data may be stored as a sorted
(alphabetically) linked list using only an additional array LINK for the nextpointer field of the
list and the variable START to point to the first record in the list. Observe that 0 is used as the
null pointer.

[Link] [Link]
 Website: [Link]

5.4 TRAVERSING A LINKED: LIST Let LIST be a linked list in memory stored in linear
arrays INFO and LINK with START point into the first element and NULL indicating the end of
LIST. Suppose we want to traverse LIST order to process each node exactly once. This section
presents an algorithm that does so and then uses the algorithm in some applications.
Our traversing algorithm uses a pointer variable PTR which points to the node that is currently
being processed. Accordingly, LINK[PTR] points to the next node to be processed. Thus the
assignment
PTR := LINK[PTR]
moves the pointer to the next node in the list, as pictured in Fig. 5.8.

The details of the algorithm are as follows. Initialize PTR or START. Then process INFO[PTR]
the information at the first node. Update PTR by the assignment PTR := LINK[PTR], so that
PTR points to the second node. Then process INFO[PTR], the information at the second node.
Again update PTR by the assignment PTR := LINK[PTR], and then process INFO[PTR], the
information at the third node. And so on. Continue until PTR = NULL, which signals the end of
the list. A formal presentation of the algorithm follows.

[Link] [Link]
 Website: [Link]
Algorithm 5.1: (Traversing a Linked List) Let LIST be a linked list in memory. This algorithm
traverses LIST, applying an operation PROCESS to each element of LIST. The variable PTR
points to the node currently being processed.
1. Set PTR := START. [Initializes pointer PTR.]
2. Repeat Steps 3 and 4 while PTR ≠ NULL.
3. Apply PROCESS to INFO[PTR].
4. Set PTR := LINK[PTR]. [PTR now points to the next node.] [End of Step 2 loop.]
5. Exit.

[Link] [Link]
 Website: [Link]
5.5 SEARCHING A LINKED LIST
Let LIST be a linked list in memory, stored as in Secs. 5.3 and 5.4. Suppose a specific ITEM of
information is given. This section discusses two searching algorithms for finding the location
LOC of the node where ITEM first appears in LIST. The first algorithm does not assume that the
data in LIST are sorted, whereas the second algorithm does assume that LIST is sorted.
If ITEM is actually a key value and we are searching through a file for the record containing
ITEM, then ITEM can appear only once in LIST.
LIST Is Unsorted: Suppose the data in LIST are not necessarily sorted. Then one searches for
ITEM in LIST by traversing through the list using aa pointer variable PTR and comparing ITEM
with the contents INFO[PTR] of each node, one by one, of LIST. Before we update the pointer
PTR by
PTR := LINK[PTR]
We require two tests. First we have to check to see whether we have reached the end of the list;
i.e first we check to see whether
PTR = NULL
If not, then we check to see whether
INFO[PTR] = ITEM
The two tests cannot be performed at the same time, since INFO[PTR] is not defined when PTR
= NULL. Accordingly, we use the first test to control the execution of a loop, and we let the
second test take place inside the loop. The algorithm follows.
Algorithm 5.2 SEARCH(INFO, LINK, START, ITEM, LOC) LIST is a linked list in memory.
This algorithm finds the location LOC of the node where ITEM first appears in LIST, or sets
LOC = NULL.
1. Set PTR := START.
2. Repeat Step 3 while PTR ≠ NULL:
3. İf ITEM = INFO[PTR], then: Set LOC := PTR, and Exit. Else: Set PTR := LINK[PTR]. [PTR
now points to the next node.] [End of If structure.] [End of Step 2 loop.]
4. [Search is unsuccessful.] Set LOC := NULL.
5. Exit.
Example 5.8 Consider the personnel file in Fig. 5.7. The following module reads the social
security number NNN of an employee and then gives the employee a 5 percent increase in
salary.

[Link] [Link]
 Website: [Link]
1. Read: NNN.
2. Call SEARCH(SSN, LINK, START, NNN, LOC).
3. If LOC ≠ NULL, then: Set SALARY[LOC] : = SALARY[LOC] + 0.05*SALARY[LOC],
Else: Write: NNN is not in file. [End of If structure.]
4. Return.
(The module takes care of the case in which there is an error in inputting the social security
number.)
LIST is Sorted Suppose the data in LIST are sorted. Again we search for ITEM in LIST by
traversing the list using a pointer variable PTR and comparing ITEM with the contents
INFO[PTR] of each node, one by one, of LIST. Now, however, we can stop once ITEM exceeds
INFO[PTR]. The algorithm follows.

5.7 INSERTION INTO A LINKED LIST

Let LIST be a linked list with successive nodes A and B, as pictured in Fig. 5.14(a). Suppose a
node N is to be inserted into the list between nodes A and B. The schematic diagram of such an
insertion appears in Fig. 5.14(b). That is, node A now points to the new node N, and node N
points to node B, to which A previously pointed.

[Link] [Link]
 Website: [Link]
Suppose our linked list is maintained in memory in the form
LIST(INFO, LINK, START, AVAIL)
Figure 5.14 does not take into account that the memory space for the new node N will come from
thy AVAIL list. Specifically, for easier processing, the first node in the AVAIL list will be used
for the new node N. Thus a more exact schematic diagram of such an insertion is that in Fig.
5.15. Observe that three pointer fields are changed as follows:
(1) The nextpointer field of node A now points to the new node N, to which AVAIL
previously pointed.

(2) AVAIL now points to the second node in the free pool, to which node N previously
pointed.
(3) The nextpointer field of node N now points to node B, to which node A previously
pointed.
There are also two special cases. If the new node N is the first node in the list, then START will
point to N; and if the new node N is the last node in the list, then N will contain the null pointer.

[Link] [Link]
 Website: [Link]
Insertion Algorithms: Algorithms which insert nodes into linked lists come up in various
situations. We discuss three of them here. The first one inserts a node at the beginning of the list,
the second one inserts a node after the node with a given location, and the third one inserts a
node into a sorted list. All our algorithms assume that the linked list is in memory in the form
LIST(INFO, LINK, START, AVAIL) and that the variable ITEM contains the new information
to be added to the list.

Since our insertion algorithms will use a node ip the AVAIL list, all of the algorithms will
include the following steps:
(a) Checking to see if space is available in the AVAIL list. If not, that is, if AVAIL = NULL.
then the algorithm will print the message OVERFLOW.
(b) Removing the first node from the AVAIL list. Using the variable NEW to keep track of the
location of the new node, this step can be implemented by the pair of assignments (in this order)
NEW := AVAIL, AVAIL := LINK[AVAIL]
(c) Copying new information into the new node. In other words,
INFO[NEW] := ITEМ
The schematic diagram of the latter two steps is pictured in Fig. 5.17.

Inserting at the Beginning of a List: Suppose our linked list is not necessarily sorted and there
is no reason to insert a new node in any special place in the list. Then the easiest place to insert
the node is at the beginning of the list. An algorithm that does so follows:

[Link] [Link]
 Website: [Link]

Steps 1 to 3 have already been discussed, and the schematic diagram of Steps 2 and 3 appears in
Fig. 5.17. The schematic diagram of Steps 4 and 5 appears in Fig. 5.18.

Example 5.14 Consider the lists of tests in Fig. 5.10. Suppose the test score 75 is to be added to
the beginning of the geometry list. We simulate Algorithm 5.4. Observe that ITEM 75, INFO =
TEST and START = GEOM.
INSFIRST(TEST, LINK, GEOM, AVAIL, ITEM)
1. Since AVAIL ≠ NULL, control is transferred to Step 2.
2. NEW = 9, then AVAIL = LINK[9] = 10.
3. TEST[9] = 75.
4. LINK[9] = 5.
5. GEOM = 9.
6. Exit.
Figure 5.19 shows the data structure after 75 is added to the geometry list. Observe that only
three pointers are changed, AVAIL, GEOM and LINK[9].

[Link] [Link]
 Website: [Link]

Inserting after a Given Node

Suppose we are given the value of LOC where either LOC is the location of a node A in a linked
LIST or LOC = NULL. The following is an algorithm which inserts ITEM into LIST so that
ITEM follows node A or, when LOC = NULL, so that ITEM is the first node.
Let N denote the new node (whose location is NEW). If LOC = NULL, then N is inserted as the
first node in LIST as in Algorithm 5.4. Otherwise, as pictured in Fig. 5.15, wè let node N point to
node B (which originally followed node A) by the assignment
LINK[NEW] := LINK[LOC]
and we let node A point to the new node N by the assignment
LINK[LOC] := NEW
Algorithm 5.5: INSLOC(INFO, LINK, START, AVAIL, LOC, ITEM)
This algorithm inserts ITEM so that ITEM follows the node with location LOC or inserts ITEM
as the first node when LOC = NULL.
1. [OVERFLOW?] If AVAIL = NULL, then: Write: OVERFLOW, and Exit.
2. [Remove first node from AVAIL list.] Set NEW := AVAIL and AVAIL := LINK[AVAIL].
3. Set INFO[NEW] := ITEM. [Copies new data into new node.]

[Link] [Link]
 Website: [Link]
4. If LOC = NULL, then: [Insert as first node.]
Set LINK[NEW] := START and START := NEW.
Else: [Insert after node with location LOC.]
Set LINK [NEW] := LINK[LOC] and LINK[LOC] := NEW. [End of If structure.]
5. Exit.
Inserting into a Sorted Linked List Suppose ITEM is to be inserted into a sorted linked LIST.
Then ITEM must be inserted between nodes A and B so that
INFO(A) < ITEM ≤ INFO(B)
The following is a procedure which finds the location LOC of node A, that is, which finds the
location LOC of the last node in LIST whose value is less than ITEM.
Traverse the list, using a pointer variable PTR and comparing ITEM with INFO[PTR] at each
node. While traversing, keep track of the location of the preceding node by using a pointer
variable SAVE, as pictured in Fig. 5.20. Thus SAVE and PTR are updated by the assignments
SAVE:= PTR and PTR := LINK[PTR]

The traversing continues as long as INFO[PTR| > ITEM. or in other words, the traversing stops
as soon as ITEM ≤ INFO[PTR]. Then PTR points to node B, so SAVE will contain the location
of the node A.
The formal statement of our procedure follows. The cases where the list is empty or where ITEM
< INFO[START], so LOC = NULL, are treated separately, since they do not involve the variable
SAVE.
Procedure 5.6: FINDA(INFO, LINK, START, ITEM, LOC) This procedure finds the location
LOC of the last node in a sorted list such that INFO[LOC] < ITEM, or sets LOC = NULL.
1. [List empty?] If START = NULL, then: Set LOC := NULL, and Return.
2. [Special case?] If ITEM < INFO[START], then: Set LOC := NULL, and Return.
3. Set SAVE := START and PTR := LINK[START]. [Initializes pointers.]
4. Repeat Steps 5 and 6 while PTR ≠ NULL.
5. If ITEM < INFO[PTR]. then:

[Link] [Link]
 Website: [Link]
Set LOC := SAVE, and Return.
[End of If structure.]
6. Set SAVE := PTR and PTR := LINK[PTR]. [Updates pointers.] [End of Step 4 loop.]
7. Set LOC := SAVE.
8. Return.
Now we have all the components to present an algorithm which inserts ITEM into a linked list.
The simplicity of the algorithm comes from using the previous two procedures.

Copying: Suppose we want to copy all or part of a given list, or suppose we want to form a new
list that is the concatenation of two given lists. This can be done by defining a null list and then
adding the appropriate elements to the list, one by one, by various insertion algorithms. A null
list is defined by simply choosing a variable name or pointer for the list, such as NAME, and
then setting NAME := NULL. These algorithms are covered in the problem sections.
5.8 DELETION FROM A LINKED LIST
Let LIST be a linked list with a node N between nodes A and B, as pictured in Fig. 5.22(a).
Suppose node N is to be deleted from the linked list. The schematic diagram of such a deletion
appears in Fig. 5.22(b). The deletion occurs as soon as the nextpointer field of node A is changed
so that it points to node B. (Accordingly, when performing deletions, one must keep track of the

[Link] [Link]
 Website: [Link]
address of the node which immediately precedes the node that is to be deleted.) Suppose our
linked list is maintained in memory in the form
LIST(INFO, LINK, START, AVAIL)

Figure 5.22 does not take into account the fact that, when a node N is deleted from our list, we
will immediately return its memory space to the AVAIL list. Specifically, for easier processing,
it will be returned to the beginning of the AVAIL list. Thus a more exact schematic diagram of
such a deletion is the one in Fig. 5.23. Observe that three pointer fields are changed as follows:
(1) The nextpointer field of node A now points to node B, where node N previously pointed.
(2) The nextpointer field of N now points to the original first node in the free pool, where
AVAIL previously pointed.
(3) AVAIL now points to the deleted node N.

There are also two special cases. If the deleted node N is the first node in the list, then START
will point to node B; and if the deleted node N is the last node in the list, then node A will
contain the NULL pointer.
Example 5.16 (a) Consider Fig. 5.21, the list of patients in the hospital ward. Suppose Green is
discharged, so that BED[8] is now empty. Then, in order to maintain the linked list, the
following three changes in the pointer fields must be executed:
LINK[11] = 10 LINK[8] = 2 AVAIL = 8
By the first change, Fields, who originally preceded Green, now points to Jones, who originally
followed Green. The second and third changes add the new empty bed to the AVAIL list. We

[Link] [Link]
 Website: [Link]
emphasize that, before making the deletion, we had to find the node BED[11], which originally
pointed to the deleted node BED[8].
(b) Consider Fig. 5.12, the list of brokers and their customers. Suppose Teller, the first customer
of Nelson, is deleted from the list of customers. Then, in order to maintain the linked lists, the
following three changes in the pointer fields must be executed:
POINT[4] = 10 LLNK[9] = 11 AVAIL = 9
By the first change, Nelson now points to his original second customer, Jones. The second and
third changes add the new empty node to the AVAIL list.
(c) Suppose the data elements E, B and C are deleted, one after the other, from the list in Fig.
5.16. The new list is pictured in Fig. 5.24. Observe that now the first three available nodes are:
INFO[3], which originally contained C
INFO[2], which originally contained B
INFO[5], which originally contained E
Observe that the order of the nodes in the AVAIL list is the reverse of the order in which the
nodes have been deleted from the list.

Deletion Algorithms Algorithms which delete nodes from linked lists come up in various
situations. We discuss two of them here. The first one delctes the node following a given node,
and the second one deletes the node with a given ITEM of information. All our algorithms
assume that the linked list is in memory in the form LIST(INFO, LINK, START, AVAIL).
All of our deletion algorithms will return the memory space of the deleted node N to the
beginning of the AVAIL list. Accordingly, all of our algorithms will include the following pair
of assignments, where LOC is the location of the deleted node N:
LINK[LOC] := AVAIL and then AVAIL := LOC

[Link] [Link]
 Website: [Link]
These two operations are pictured in Fig. 5.25.

Some of our algorithms may want to delete either the first node or the last node from the list. An
algorithm that does so must check to see if there is a node in the list. If not, i.e., if START =
NULL, then the algorithm will print the message UNDERFLOW.

[Link] [Link]
 Website: [Link]
The simplicity of the algorithm comes from the fact that we are already given the location LOCP
of the node which precedes node N. In many applications, we must first find LOCP.
Deleting the Node with a Given ITEM of Information: Let LIST be a linked list in memory.
Suppose we are given an ITEM of information and we want to delete from the LIST the first
node N which contains ITEM. (If ITEM is a key value, then only one node can contain ITEM.)
Recall that before we can delete N from the list, we need to know the location of the node
preceding N. Accordingly, first we give a procedure which finds the location LOC of the node N
containing ITEM and the location LOCP of the node preceding node N: If N is the first node, we
set LOCP = NULL, and if ITEM does not appear in LIST, we set LOC = NULL. (This procedure
is similar to Procedure 5.6.) Traverse the list, using a pointer variable PTR and comparing ITEM
with INFO[PTR] at each node. While traversing, keep track of the location of the preceding node
by using a pointer variable SAVE, as pictured in Fig. 5.20. Thus SAVE and PTR are updated by
the assignments
SAVE := PTR and PTR := LINK[PTR]
The traversing continues as long as INFO[PTR] ≠ ITEM, or in other words, the traversing stops
as Soon as ITEM = INFO[PTR]. Then PTR contains the location LOC of node N and SAVE
contains the location LOCP of the node preceding N.
The formal statement of our procedure follows. The cases where the list is empty or where
INFO[START] = ITEM (i.e., where node N is the first node) are treated separately, since they do
not involve the variable SAVE.

Remark: The reader may have noticed that Steps 3 and 4 in Algorithm 5.10 already appear in
Algorithm 5.8. In other words, we could replace the steps by the following Call statement: Call
DEL(INFO, LINK, START, AVAIL, LOC, LOCP).

[Link] [Link]
 Website: [Link]
Example 5.17 Consider the list of patients in Fig. 5.21. Suppose the patient Green is discharged.
We simulate Procedure 5.9 to find the location LOC of Green and the location LOCP of the
patient preceding Green. Then we simulate Algorithm 5.10 to delete Green from the list. Here
ITEM = Green, INFO = BED, START = 5 and AVAIL = 2.

(a) FINDB(BED, LINK, START, ITEM, LOC, LOCP)

1. Since START ≠ NULL, control is transferred to Steр 2.
2. Since BED[5] = Adams ≠ Green, control is transferred
3. SAVE = 5 and PTR = LINK[5] = 3.
4. Steps 5 and 6 are repeated as follows:

(b) DELLOC(BED, LINK, START, AVAIL, ITEM)

1. Call FINDB(BED, LINK, START, ITEM, LOC, LOCP). [Hence LOC = 8 and LOCP 11.]
2. Since LOC ≠ NULL, control is transferred to Step 3.
3. Since LOCP ≠ NULL, we have: LINK[11] = LINK[8] = 10.
4. LINK[8] = 2 and AVAIL = 8.
5. Exit.
Figure 5.28 shows the data structure after Green is removed from the patient list. We emphasize
that only three pointers have been changed, LINK[11], LINK[8] and AVAIL.

[Link] [Link]
 Website: [Link]
5.9 HEADER LINKED LISTS
A header linked list is a linked list which always contains a special node, called the header node,
at the beginning of the list. The following are two kinds of widely used header lists:
(1) A grounded header list is a header list where the last node contains the null pointer. (The term
"grounded" comes from the fact that many texts use the electrical ground symbol to indicate the
null pointer.)
(2) A circular header list is a header list where the last node points back to the header node.
Figure 5.29 contains schematic diagrams of these header lists. Unless otherwise stated or
implied. our header lists will always be circular. Accordingly, in such a case, the header node
also acts as a sentinel indicating the end of the list.

Observe that the list pointer START always points to the header node. Accordingly,
LINK[START] = NULL indicates that a grounded header list is empty, and LINK[START] =
START indicates that a circular header list is empty.
Although our data may be maintained by header lists in memory, the AVAIL list will always be
maintained as an ordinary linked list.

[Link] [Link]
 Website: [Link]

The term "node," by itself, normally refers to an ordinary node, not the header node, when used
with header lists. Thus, the first node in a header list is the node following the header node, and
the location of the first node is LINK[START],
Algorithm 5.11, which not START. as with ordinary linked lists. the same as Algorithm 5.1, uses
a pointer variable PTR to traverse a circular header list, is essentially (1) begins with PTR =
LINK(START] which traverses an ordinary linked list, except that now the algorithm PTR (not
PTR = START) and (2) ends when PTR = START (not = NULL).
Circular header lists are frequently used instead of ordinary linked lists because many operations
are much easier to state and implement using header lists. This comes from the following two
properties of circular header lists:
(1)The null pointer is not used, and hence all pointers contain valid addresses.
(2) Every (ordinary) node has a predecessor, so the first node may not require a special case. The
next example illustrates the usefulness of these properties.
Algorithm 5.11: (Traversing a Circular Header List) Let LIST be a circular header list memory.
This algorithm traverses LIST, applying an operation PROCESS each node of LIST.
1. Set PTR := LINK[START]. [Initializes the pointer PTR.]

[Link] [Link]
 Website: [Link]
2. Repeat Steps 3 and 4 while PTR ≠ START:
3. Apply PROCESS to INFO[PTR].
4. Set PTR := LINK[PTR]. [PTR now points to the next node.] [End of Step 2 loop.]
5. Exit.

Remark: There are two other variations of linked lists which sometimes appear in the literature:
(1) pointer, A linked called list whose a circular last list node points back to the first node instead
of containing the null
(2) A linked list which contains both a special header node at the beginning of the list and a
special trailer node at the end of the list Figure 5.31 contains schematic diagrams of these lists.

[Link] [Link]
 Website: [Link]
5.10 TWO-WAY LISTS
Each list discussed above is called a one-way list, since there is only one way that the list can be
traversed. That is, beginning with the list pointer variable START, which points to the first node
or the header node, and using the nextpointer field LINK to point to the next node in the list, we
can traverse the list in only one direction. Furthermore, given the location ĽOC of a node N in
such a

list, one has immediate access to the next node in the list (by evaluating LINK[LOC]), but one
does not have access to the preceding node without traversing part of the list. This means, in
particular, that one must traverse that part of the list preceding N in order to delete N from the
list.
This section introduces a new list structure, called a two-way list, which can be traversed in two
directions: in the usual forward direction from the beginning of the list to the end, or in the
backward direction from the end of the list to the beginning. Furthermore, given the location
LOC node a node in the N in the list, one now has immediate access to both the next node and
the preceding traversing any list. part This of the means, list. in particular, that one is able to
delete N from the list without traversing any part of the list.
A two-way into three list parts: is a linear collection of data elements, called nodes, where each
node N is divided into three parts:
(1) An information field INFO which contains the data of N
(2) A pointer field FORW which contains the location of the next node in the list.
(3) A pointer field BACK which contains the location of the preceding node in the list.
The list also requires two list pointer variables: FIRST, which points to the first node in the list.
and LAST, which points to the last node in the list. Figure 5.33 contains a schematic diagram of

[Link] [Link]
 Website: [Link]
such a list. Observe that the null pointer appears in the FORW field of the last node in the list
and also in the BACK field of the first node in the list.

Observe that, using the variable FIRST and the pointer field FORW, we can traverse a two-way
list in the forward direction as before. On the other hand, using the variable LAST and the
pointer field BACK, we can also traverse the list in the backward direction.
Suppose LOCA and LOCB are the locations, respectively, of nodes A and B in a two-way list.
Then the way that the pointers FORW and BACK are defined gives us the following:
Pointer property: FORW[LOCA] = LOCB if and only if BACK[LOCB] = LOСА
In other words, the statement that node B follows node A is equivalent to the statement that node
A precedes node B.
Two-way lists may be maintained in memory by means of linear arrays in the same way as one
way lists except that now we require two pointer arrays, FORW and BACK, instead of one
pointer array LINK, and we require two list pointer variables, FIRST and LAST, instead of one
list pointer variable START. On the other hand, the list AVAIL of available space in the arrays
will still be maintained as a one-way list-using FORW as the pointer field-since we delete and
insert nodes only at the beginning of the AVAIL list.
Operations on Two-Way Lists

Traversing: Suppose we want to traverse LIST in order to process each node exactly once. Then
we can use Algorithm 5.1 if LIST is an ordinary two-way list, or we can use Algorithm 5.11 if

[Link] [Link]
 Website: [Link]
LIST contains a header node. Here it is of no advantage that the data are organized as a two-way
list rather than as a one-way list.
Searching: Suppose we are given an ITEM of information-—a key value-and we want to find
the location LOC of ITEM in LIST. Then we can use Algorithm 5.?. if LIST is an ordinary two-
way list, or we can use Algorithm 5.12 if LIST has a header node. Here the main advantage is
that we can search for ITEM in the backward direction if we have reason to suspect that ITEM
appears near the end of the list. For example, suppose LIST is a list of names sorted
alphabetically. If ITEM = Smith. then we would search LIST in the backward direction, but if
ITEM = Davis, then we would search LIST in' the forward direction.
Deleting: Suppose we are given the location LOC of a node N in LIST, and suppose we want to
delete N from the list. We assume that LIST is a two-way circular header list. Note that
BACK[LOC] and FORW[LOC] are the locations, respectively, of the nodes which precede and
follow node N. Accordingly, as pictured in Fig. 5.37, N is deleted from the list by changing the
following pair of pointers:

FORW[BACK[LOC]] := FORW[LOC] and BACK[FORW[LOC]] := BACK[LOC)

The deleted node N is then returned to the AVAIL list by the assignments:
FORW[LOC] := AVAIL and AVAIL := LOC
The formal statement of the algorithm follows.
Algorithm 5.15: DELTWL(INFO, FORW, BACK, START, AVAIL, LOС)
1. [Delete node.]
Set FORW[BACK[LOC]] := FORW[LOC] and
BACK[FORW[LOC]] := BACK[LOC].
2. [Return node to AVAIL list.]
Set FORW[LOC] := AVAIL and AVAIL := LOC.
3. Exit.
Here we see one main advantage of a two-way list: If the data were organized as a one-way list,
then, in order to delete N, we would have to traverse the one-way list to find the location of the
node preceding N.

[Link] [Link]
 Website: [Link]
Inserting: Suppose we are given the locations LOCA and LOCB of adjacent nodes A and B in
LIST, and suppose we want to insert a given ITEM of imormation between nodes A and B. As
with a oneway list, first we remove the first node N from the AVAIL list, using the variable
NEW to keep track of its location, and then we copy the data ITEM into the node N; that is, we
set: NEW := AVAIL, AVAIL := FORW[AVAIL], INFO[NEW] := ITEM
Now, as pictured in Fig. 5.38, the node N with contents ITEM is inserted into the list by
changing the following four pointers:
FORW[LOCA] := NEW, FORW[NEW] := LOCВ
BACK[LOCB] := NEW, BACK[NEW] := LOCА
The formal statement of our algorithm follows.
Algorithm 5.16: INSTWL(INFO, FORW, BACK, START, AVAIL, LOCA, LOCB, ITEM)
1. [OVERFLOW?] If AVAIL = NULL, then: Write: OVERFLOW, and Exit.
2.[Remove node from AVAIL list and copy new data into node.]
Set NEW := AVAIL, AVAIL:= FORW[AVAIL], INFO[NEW] := ITEМ.

3. Insert node into list.]

Set FORW[LOCA] := NEW, FORW[NEW] := LOCB,
BACK[LOCB] := NEW, BACK[NEW] := LOCA.
4. Exit.
Algorithm 5.16 assumes that LIST contains a header node. Hence LOCA or LOCB may point to
the header node, in which case N will be inserted as the first node or the last node. If LIST does
not contain a header node, then we must consider the case that LOCA = NULL and N is inserted
as the first node in the list, and the case that LOCB = NULL and N is inserted as the last node in
the list. Remark: Generally speaking, storing data as a two-way list, which requires extra space
for the backward pointers and extra time to change the added pointers, rather than as a one-way

[Link] [Link]
 Website: [Link]
list is not worth the expense unless one must frequently find the location of the node which
precedes a given node N, as in the deletion above.
Trees: Binary trees, traversing binary trees
7.2 BINARY TREES A binary tree T is defined as a finite set of elements, called nodes, such
that:
(a) T is empty (called the null tree or empty tree), or
(b) T contains a distinguished node R, called the root of T, and the remaining nodes of T form an
ordered pair of disjoint binary trees T1 and T₂.
If T does contain a root R, then the two trees T and T2 are called, respectively, the left and right
subtrees of R. If T is nonempty, then its root is called the left successor of R; similarly, if T₂ is
nonempty, then its root is called the right successor of R.
A binary tree T is frequently presented by means of a diagram. Specifically, the diagram in Fig.
7.1 represents a binary tree T as follows. (i) T consists of 11 nodes, represented by the letters
through L, excluding 1. (ii) The root of T is the node A at the top of the diagram. (iii) A left- A
downward slanted line from a node N indicates a left successor of N, and a right-downward
slanted line from N indicates a right successor of N. Observe that:
(a) B is a left successor and C is a right successor of the node А.
(b) The left subtree of the root A consists of the nodes B, D, E and F, and the right subtree of A
consists of the nodes C, G, H,J, K and L.

Any node N in a binary tree T has either 0, 1 or 2 successors. The nodes A, B, Cand H have two
successors, the nodes E and J have only one successor, and the nodes D, F, G, L and K have no
successors. The nodes with no successors are called terminal nodes.
The above definition of the binary tree T is recursive since Tis defined in terms of the binary
subtrees T, and T₂. This means, in particular, that every node N of T contains a left and a right
subtree. Moreover, if N is a terminal node, then both its left and right subtrees are empty.
Binary trees T and T' are said to be similar if they have the same structure or, in other words, if
they have the same shape. The trees are said to be copies if they are similar and if they have the
same contents at corresponding nodes.

[Link] [Link]
 Website: [Link]
Linked Representation of Binary Trees: Consider a binary tree T. Unless otherwise stated or
implied, T will be maintained in memory by means of a linked representation which uses three
parallel arrays, INFO, LEFT and RIGHT, and a pointer variable ROOT as follows. First of all,
each node N of T will correspond to a location K such that:
(1) INFO[K] contains the data at the node N.
(2) LEFT[K] contains the location of the left child of node N.
(3) RIGHT[K] contains the location of the right child of node N.
Furthermore, ROOT will contain the location of the root R of T. If any subtree is empty, then the
corresponding pointer will contain the null value; if the tree T itself is empty, then ROOT will
contain the null value.
Remark 1: Most of our examples will show a single item of information at each node N of a
binary tree T. In actual practice, an entire record may be stored at the node N. In other words,
INFO may actually be a linear array of records or a collection of parallel arrays.
Remark 2: Since nodes may be inserted into and deleted from our binary trees, we also implicitly
assume that the empty locations in the arrays INFO, LEFT and RIGHT form a linked list with
pointer AVAIL, as discussed in relation to linked lists in Chap. 5. We will usually let the LEFT
array contain the pointers for the AVAIL list.
Remark 3: Any invalid address may be chosen for the null pointer denoted by NULL. In actual
practice, 0 or a negative number is used for NULL. (See Sec. 5.2.)

Example 7.4 Suppose the personnel file of a small company contains the following data on its
nine employees:
Name, Social Security Number, Sex, Monthly Salary
Figure 7.8 shows how the file may be maintained in memory as a binary tree. Compare this data
structure with Fig. 5.12, where the exact same data are organized as a one-way list.
Suppose we want to draw the tree diagram which corresponds to the binary tree in Fig. 7.8. For
notational convenience, we label the nodes in the tree diagram only by the key values NAME.
We construct the tree as follows:
(a) The value ROOT = 14 indicates that Harris is the root of the tree.
(b) LEFT[14] = 9 indicates that Cohen is the left child of Harris, and RIGHT[14] = 7 indicates
that Lewis is the right child of Harris.
Repeating Step (b) for each new node in the diagram, we obtain Fig. 7.9.

[Link] [Link]
 Website: [Link]

Sequential Representation of Binary Trees: Suppose T is a binary tree that is complete or

nearly complete. Then there is an efficient way of maintaining T in memory called the sequential
representation of T. This representation uses only a single linear array TREE as follows:
(a) The root R of T is stored in TREE[1].
(b) child If a node N occupies TREE[K], then its left child is stored in TREE[2 *K] and its right
is stored in TREE[2*K + 1].
Again, tree NULL is empty. is used to indicate an empty subtree. In particular, TREE[1] =
NULL indicates that the tree is empty.

[Link] [Link]
 Website: [Link]
The sequential representation of the binary tree T in Fig. 7.10(a) is shown in Fig. 7.10(b).
Although the tree T contains only 9 nodes, we require 14 locations in the array TREE to
represent it. In fact, if we included null entries for all successors of the terminal nodes, we would
actually require up to TREE[29] for the right successor of TREE[14].

In general, the sequential representation of a tree with depth d will require an array with
approximately 2d+1 elements. Accordingly, this sequential representation is usually inefficient
unless, as stated above, the binary tree T is complete or nearly complete. For example, the tree T
in Fig. 7.1 has 11 nodes and depth 5, which means it would require an array with approximately
29 = 64 elements.
7.4 TRAVERSING BINARY TREES There are three standard ways of traversing a binary tree
T with root R. These three algorithms, called preorder, inorder and postorder, are as follows:
Preorder:
(1) Process the root R.
(2) Traverse the left subtree of R in preorder.
(3) Traverse the right subtree of R in preorder.
Inorder:
(1) Traverse the left subtree of R in inorder.
(2) Process the root R.
(3) Traverse the right subtree of R in inorder.

[Link] [Link]
 Website: [Link]
Postorder:
(1) Traverse the left subtree of R in postorder.
(2) Traverse the right subtree of R in postorder.
(3) Process the root R.
Observe that each algorithm contains the same three steps, and that the left subtree of R is always
traversed before the right subtree. The difference between the algorithms is the time at which the
root R is processed. Specifically, in the "pre" algorithm, the root R is processed before the
subtrees are traversed; in the "in" algorithm, the root R is processed between the traversals of the
subtrees: and in the "post" algorithm, the root R is processed after the subtrees are traversed.
The three algorithms are sometimes called, respectively, the node-left-right (NLR) traversal, the
left-node-right (LNR) traversal and the left-right-node (LRN) traversal.
Observe that each of the above traversal algorithms is recursively defined, since the algorithm
involves traversing subtrees in the given order. Accordingly, we will expect that a stack will be
used when the algorithms are implemented on the computer.

[Link] [Link]
 Website: [Link]

Preorder Traversal Using Stack:

[Link] [Link]
 Website: [Link]
Solution:

[Link] [Link]
 Website: [Link]
Inorder Traversal Using Stack:

Solution:

[Link] [Link]
 Website: [Link]
Postorder Traversal Using Stack: Consider again the binary tree T in Fig. 7.17. We simulate
the above algorithm with T, showing the contents of STACK.
Solution:

[Link] [Link]
 Website: [Link]
Binary search trees: Various operations\
This structure enables one to search for and find an element with an average running time f(n) =
O(log2 n). It also enables one to easily insert and delete elements. This structure contrasts with
the following structures:
(a) Sorted linear array: Here one can search for and find an element with a running time f(n) =
O(log2 n), but it is expensive to insert and delete elements.
(b) Linked list: Here one can easily insert and delete elements, but it is expensive to search for
and find an element, since one must use a linear search with running time f(n) = O(n).
Although each node in a binary search tree may contain an entire record of data, the definition of
the binary tree depends on a given field whose values are distinct and may be ordered.
Suppose T is a binary tree. Then T is called a binary search tree (or binary sorted tree) if each
node N of T has the following property: The value at N is greater than every value in the left
subtree of N and is less than every value in the right subtree of N. (It is not difficult to see that
this property guarantees that the inorder traversal of T will yield a sorted listing of the elements
of T.)
Example:

7.8 SEARCHING AND INSERTING IN BINARY SEARCH TREES

Suppose T is a binary search tree. This section discusses the basic operations of searching and
inserting with respect to T. In fact, the searching and inserting will be given by a single search

[Link] [Link]
 Website: [Link]
and insertion algorithm. The operation of deleting is treated in the next section. Traversing in T
is the same as traversing in any binary tree; this subject has been covered in Seс. 7.4.
Suppose an ITEM of information is given. The following algorithm finds the location of ITEM
in the binary search tree T, or inserts ITEM as a new node in its appropriate place in the tree.
(a) Compare ITEM with the root node N of the tree:
(i) If ITEM < N, proceed to the left child of N.
(ii) If ITEM > N, proceed to the right child of N.
(b) Repeat Step (a) until one of the following occurs:
(i) We meet a node N such that ITEM = N. In this case the search is successful.
(ii) We meet an empty subtree, which indicates that the search is unsuccessful, and we
insert ITEM in place of the empty subtree. In other words, proceed from the root R down
through the tree T until finding ITEM in T or inserting ITEM as a terminal node in T.
Example 7.14
(a) Consider the binary search tree T in Fig. 7.21. Suppose ITEM = 20 is given. Simulating the
above algorithm, we obtain the following steps:
1. Compare ITEM = 20 with the root, 38, of the tree T. Since 20 < 38, proceed to the left child of
38, which is 14.
2. Compare ITEM = 20 with 14. Since 20 > 14, proceed to the right child of 14, which is 23.
3. Compare ITEM = 20 with 23. Since 20 < 23, proceed to the left child of 23. which is 18.
4. Compare ITEM = 20 with 18. Since 20 > 18 and 18 does not have a right child, insert 20 as
the right child of 18.
Figure 7.22 shows the new tree with ITEM = 20 inserted. The shaded edges indicate the path
down through the tree during the algorithm.
(b) Consider the binary search tree T in Fig. 7.9. Suppose ITEM = Davis is given. Simulating the
above algorithm, we obtain the following steps:

[Link] [Link]
 Website: [Link]
1. Compare ITEM = Davis with the root of the tree, Harris. Since Davis < Harris, proceed to the
left child of Harris, which is Cohen.
2. Compare ITEM = Davis with Cohen. Since Davis > Cohen, proceed to the right child of
Cohen, which is Green.
3. Compare ITEM = Davis with Green. Since Davis< Green, proceed to the left child of Green,
which is Davis.
4. Compare ITEM = Davis with the left child, Davis. We have found the location of Davis in the
tree.
Example 7.15 Suppose the following six numbers are inserted in order into an empty binary
search tree:
40, 60, 50, 33, 55, 11
Figure 7.23 shows the six stages of the tree. We emphasize that if the six numbers were given in
a different order, then the tree might be different and we might have a different depth.

[Link] [Link]
 Website: [Link]

[Link] [Link]
 Website: [Link]

Observe that, in Step 4, there are three possibilities: (1) the tree is empty, (2) ITEM is added as a
left child and (3) ITEM is added as a right child.
7.9 DELETING IN A BINARY SEARCH TREE
Suppose T is a binary search tree, and suppose an ITEM of information is given. This section
gives an algorithm which deletes ITEM from the tree T. The deletion algorithm first uses
Procedure 7.4 to find the location of the node N which contains ITEM and also the location of
the parent node P(N). The way N is deleted from the tree depends primarily on the number of
children of node N. There are three cases: Case 1. N has no children. Then N is deleted from T
by simply replacing the location of N in the parent node P(N) by the null pointer.
Case 2. N has exactly one child. Then N is deleted from T by simply replacing the location of N
in P(N) by the location of the only child of N.
Case 3. N that has S(N) two does children. Let S(N) denote the inorder successor of N. (The
reader can verify from T (by using not have a left child.) Then N is deleted from T by first
deleting S(N) Case 1 or Case 2) and then replacing node N in T by the node S(N).
Observe the memory that space the third case is much more complicated than the first two cases.
In all three cases, of the deleted node N is returned to the AVAIL list.

[Link] [Link]
 Website: [Link]
Example 7.18
Consider the binary search tree in Fig. 7.25(a). Suppose T appears in memory as in Fig. 7.25(b).

(a) Suppose we delete node 44 from the tree T in Fig. 7.25. Note that node 44 has no children.
Figure 7.26(a) pictures the tree after 44 is deleted, and Fig. 7.26(b) shows the linked
representation in memory. The deletion is accomplished by simply assigning NULL to the parent
node, 33. (The shading indicates the changes.)
(b) Suppose we delete node 75 from the tree T in Fig. 7.25 instead of node 44. Note that node 75
has only one child. Figure 7.27(a) pictures the tree after 75 is deleted, and Fig. 7.27(b) shows the
linked representation. The deletion is accomplished by changing the right pointer of the parent
node 60, which originally pointed to 75, so that it now points to node 66, the only child of 75.
(The shading indicates the changes.)

[Link] [Link]
 Website: [Link]

(c) Suppose we delete node 25 from the tree T in Fig. 7.25 instead of node 44 or node 75. Note
that node 25 has two children. Also observe that node 33 is the inorder successor of node 25.
Figure 7.28(a) pictures the tree after 25 is deleted, and Fig. 7.28(b) shows the linked
representation. The deletion is accomplished by first deleting 33 from the tree and then replacing
node 25 by node 33. We emphasize that the replacement of node 25 by node 33 is executed in
memory only by changing pointers, not by moving the contents of a node from one location to
another. Thus 33 is still the value of INFO[1].

[Link] [Link]
 Website: [Link]
Our deletion algorithm will be stated in terms of Procedures 7.6 and 7.7, which follow. The first
procedure refers to Cases 1 and 2, where the deleted node N does not have two children; and the
second procedure refers to Case 3, where N does have two children. There are many subcases
which reflect the fact that N may be a left child, a right child or the root. Also, in Case 2, N may
have a left child or a right child.
Procedure 7.7 treats the case that the deleted node N has two children. We note that the inorder
successor of N can be found by moving to the right child of N and then moving repeatedly to the
left until meeting a node with an empty left subtree.

[Link] [Link]
 Website: [Link]

We can now formally state our deletion algorithm, using Procedures 7.6 and 7.7 as building
blocks.
Algorithm 7.8: DEL(INFO, A LEFT, RIGHT, ROOT, AVAIL, ITEM) binary search tree T is in
memory, and an ITEM of information is given. This algorithm deletes ITEM from the tree.
1. [Find Call the locations of ITEM and its parent, using Procedure 7.4.]
2. [ITEM FIND(INFO, LEFT, RIGHT, ROOT, ITEM, LOC, PAR). in tree?] If LOC = NULL,
then: Write: ITEM not in tree, and Exit.
3. [Delete node containing ITEM.)
If RIGHT[LOC] ≠ NULL and LEFT[LOC] ≠ NULL, then:
Call CASEB(INFO, LEFT, RIGHT, ROOT, LOC, PAR).

[Link] [Link]
 Website: [Link]
Else:
Call CASEA(INFO, LEFT, RIGHT, ROOT, LOC, PAR).
[End of If structure.]
4. [Return deleted node to the AVAIL list.]
Set LEFT[LOC] := AVAIL and AVAIL := LOС.
5. Exit.
Binary heaps: Heap sort
This section discusses another tree structure, called a heap. The heap is used in an elegant sorting
algorithm called heapsort.
Suppose H is a complete binary tree with n elements. (Unless otherwise stated, we assume that H
is maintained in memory by a linear array TREE using the sequential representation of H, not a
linked representation.) Then H is called a heap, or a maxheap, if each node N of H has the
following property: The value at N is greater than or equal to the value at each of the children of
N. Accordingly, the value at N is greater than or equal to the value at any of the descendants of
N. (A minheap is defined analogously: The value at N is less than or equal to the value at any of
the children of N.)
Procedure 7.9: INSHEAP(TREE, N, ITEM)
A heap H with N elements is stored in the array TREE, and an ITEM of information is given.
This procedure inserts ITEM as a new element of H. PTR gives the location of ITEM as it rises
in the tree, and PAR denotes the location of the parent of ITEM.
1.[Add new node to H and initialize PTR.]
Set N:= N + 1 and PTR := N.
2. [Find location to insert ITEM.]
Repeat Steps 3 to 6 while PTR < 1.
3. Set PAR := PTR/2]. [Location of parent node.]
4. If ITEM ≤ TREE[PAR], then:
Set TREE[PTR] := ITEM, and Return.
[End of If structure.]
5. Set TREE[PTR] := TREE[PAR]. [Moves node down.]
6. Set PTR := PAR. [Updates PTR.]

[Link] [Link]
 Website: [Link]
[End of Step 2 loop.]
7. [Assign ITEM as the root of H.]
Set TREE[I] := ITEM.
8. Return.
Procedure 7.10: DELHEAP(TREE, N, ITEM)
A heap H with N elements is stored in the array TREE. This procedure assigns the root TREE[1]
of H to the variable ITEM and then reheap the remaining elements. The variable LAST saves the
value of the original last node of H. The pointers PTR, LEFT, and RIGHT give the locations of
LAST and its left and right children as LAST sinks in the tree.
1. Set ITEM := TREE[1].
[Removes root of H.]
2. Set LAST := TREE[N] and N := N - 1.
[Removes last node of H.]
3. Set PTR := 1, LEFT := 2 and RIGHT := 3.
[Initializes pointers.]
4. Repeat Steps 5 to 7 while RIGHT ≤ N:
5. If LAST ≥ TREE[LEFT] and LAST ≥ TREE[RIGHT], then:
Set TREE[PTR] := LAST and Return.
[End of If structure.]
6. If TREE[RIGHT] ≤ TREE[LEFT], then:
Set TREE[PTR] := TREE[LEFT] and PTR := LEFT.
Else:
Set TREE[PTR] := TREE[RIGHT] and PTR := RIGHT.
[End of If structure.]
7. Set LEFT := 2*PTR and RIGHT := LEFT + 1.
[End of Step 4 loop.]
8. If LEFT = N and LAST < TREE[LEFT], then:
Set PTR := LEFT.
9. Set TREE[PTR] := LAST.
10. Return.

[Link] [Link]
 Website: [Link]

Suppose an array A with N elements is given. The heapsort algorithm to sort A consists of the
two following phases:
Phase А: Build a heap H out of the elements of А.
Phase B: Repeatedly delete the root element of H.
Since the root of H always contains the largest node in H, Phase B deletes the elements of A in
decreasing order. A formal statement of the algorithm, which uses Procedures 7.9 and 7.10,
follows.
Algorithm 7.11: HEAPSORT(A, N)
An array A with N elements is given. This algorithm sorts the elements of A.
1. [Build a heap H, using Procedure 7.9.]
Repeat for J = 1 to N - 1:
Call INSHEAP(A, J, A[J + 1]).
[End of loор.]
2. [Sort A by repeatedly deleting the root of H, using Procedure 7.10.]
Repeat while N > 1:
(a) Call DELHEAP(A, N, ITEM).
(b) Set A[N + 1] := ITEM.
[End of Loop.]
3. Exit.
The purpose of Step 2(b) is to save space. That is, one could use another array B to hold the
sorted elements of A and replace Step 2(b) by ,
Set B[N + 1] := ITEM
However, the reader can verify that the given Step 2(b) does not interfere with the algorithm,
since A[N + 1] does not belong to the heap H.

Huffman’s algorithm
Recall that an extended binary tree or 2-tree is a binary tree T in which each node has either 0 or
children. The nodes with 0 children are called external nodes, and the nodes with 2 children a
called internal nodes. Figure 7.62 shows a 2-tree where the internal nodes are denoted by circl
and the external nodes are denoted by squares. In any 2-tree, the number NE of external nodes is
more than the number N, of internal nodes; that is,
NE = Nl + 1

[Link] [Link]
 Website: [Link]
For example, for the 2-tree in Fig. 7.62, N; = 6, and NE = Nl + 1 = 7.

Frequently, an algorithm can be represented by a 2-tree T where the internal nodes represe tests
and the external nodes represent actions. Accordingly, the running time of the algorithm ma y
depend on the lengths of the paths in the tree. With this in mind, we define the external path leng
LE of a 2-tree T to be the sum of all path lengths summed over each path from the root R of T to
external node. The internal path length L₁ of T is defined analogously, using internal nodes
instead of external nodes. For the tree in Fig. 7.62,
LE = 2 +2+3+4+4 + 3 + 3 = 21 and Ll = 0 + 1 + 1+2+3+2 = 9
Observe that,
Ll+ 2n = 9+2·6 = 9+ 12 = 21 = LE
where n = 6 is the number of internal nodes. In fact, the formula
LE = L₁+ 2n
is true for any 2-tree with n internal nodes.
Suppose T is a 2-tree with n external nodes, and suppose each of the external nodes is assigned
(nonnegative) weight. The (external) weighted path length P of the tree T is defined to be the
sum of the weighted path lengths; i.e.,
P = W1L1+ W2L2 + … + WnLn
where Wi and Li denote, respectively, the weight and path length of an external node Ni.
Consider now the collection of all 2-trees with n external nodes. Clearly, the complete tree
among them will have a minimal external path length LE. On the other hand, suppose each tree is
given the same n weights for its external nodes. Then it is not clear which tree will give a
minimal weighted path length P.

[Link] [Link]
 Website: [Link]
Example 7.36:
Figure 7.63 shows three 2-trees, T₁, T₂ and T3, each having external nodes with weights 2, 3, 5
and 11. The weighted path lengths of the three trees are as follows:
P₁= 2.2 +3.2+5.2+11.2= 42
P2 = 2.1 +3.3+5.3+11.2= 48
P3 = 2.3+3.3+5.2+11.1= 36

The quantities P1 and P3 indicate that the complete tree need not give a minimum length P, and
the quantities P₂ and P3 indicate that similar trees need not give the same lengths.

The general problem that we want to solve is as follows. Suppose a list of n weights is given:
W1, W2,..., W. Among all the 2-trees with n external nodes and with the given n weights, find a
tree T with a minimum-weighted path length. (Such a tree T is seldom unique.) Huffman gave an
algorithm, which we now state, to find such a tree T. Observe that the Huffman algorithm is
recursively defined in terms of the number of weights and the solution for one weight is simply
the tree with one node. On the other hand, in practice, we use an equivalent iterated form of the
Huffman algorithm constructing the tree from the bottom up rather than from the top down.
Huffman's Algorithm:
Suppose weights w1 and w₂ are two minimum weights among the n given weights w1,w2,w3…
wn. Find a tree T' which gives a solution for the n - 1 weights:
W₁+ W2, W3, W4,..., Wn
Then, in the tree T', replace the external node

[Link] [Link]
 Website: [Link]
Example 7.37: Suppose A, B, C, D, E, F, G and Hare 8 data items, and suppose they are
assigned weights as follows:
Data item: A B C D E F G H
Weight: 22 5 11 19 2 11 25 5
Figure 7.64(a) through (h) shows how to construct the tree T with minimum-weighted path
length using the above data and Huffman's algorithm. We explain each step separately.
(a) Here each data item belongs to its own subtree. Two subtrees with the smallest possible
combination of weights, the one weighted 2 and one of those weighted 5, are shaded.
(b) Here the subtrees that were shaded in Fig. 7.64(a) are joined together to form a subtree with
weight 7. Again, the current two subtrees of lowest weight are shaded.
(c) to (g) Each step joins together two subtrees having the lowest existing weights (always the
ones that were shaded in the preceding diagram), and again, the two resulting subtree of lowest
weight are shaded.
(h) This is the final desired tree T, formed when the only two remaining subtrees are joined
together.

Computer Implementation of Huffman's Algorithm: Consider again the data in Example

7.37. Suppose we want to implement the Huffman algorithm using the computer. First of all, we
require an extra array WT to hold the weights of the nodes; i.e., our tree will be maintained by
four parallel arrays, INFO, WT, LEFT and RIGHT. Figure 7.65(a) shows how the given data
may be stored in the computer initially. Observe that there is sufficient room for the additional
nodes. Observe that NULL appears in the left and right pointers for the initial nodes, since these
nodes will be terminal in the final tree.

[Link] [Link]
 Website: [Link]

Fig. 7.64 Building a Huffman Tree

[Link] [Link]
 Website: [Link]
During the execution of the algorithm, one must be able to keep track of all the different subtrees
and one must also be able to find the subtrees with minimum weights. This may be accomplished
by maintaining an auxiliary minheap, where each node contains the weight and the location is
used rather of the than root of a maxheap a current subtree. The initial minheap appears in Fig.
7.65(b). (The minheap the heap.) since we want the node with the lowest weight to be on the top
of the heap.)

Index INFO WT LEFT RIGHT Index INFO WT LEFT RIGHT

1 A 22 0 0 1 A 22 0 0

2 B 5 0 0 2 B 5 0 0

3 C 11 0 0 3 C 11 0 0

4 D 19 0 0 4 D 19 0 0

5 E 2 0 0 5 E 2 0 0

6 F 11 0 0 6 F 11 0 0

7 G 25 0 0 7 G 25 0 0

8 H 5 0 0 8 H 5 0 0

9 7 5 2 9 10

10 12 8 9 10 11

11 22 6 3 11 12

12 31 10 4 12 13

13 44 1 11 13 14

14 56 7 12 14 15

15 100 13 14 15 16

16 16 0

ROOT = 15, AVAIL = 16 (c) AVAIL = 9 (a)

[Link] [Link]
 Website: [Link]

The first step in building the required Huffman tree T involves the following substeps:

(i)Remoye the node N₁ = [2, 5] and the node N2 = [5, 2] from the heap. (Each time a node is deleted, one
must reheap.)

(ii) Use the data in N1 and N2 and the first available space AVAIL = 9 to add a new node as follows:

WT[9] = 2+5 = 7 LEFT[9] = 5 RIGHT[9] = 2

Thus N1 is the left child of the new node and N₂ is the right child of the new node.

(iii) Adjoin the weight and location of the new node, that is, [7, 9], to the heap.

The shaded area in Fig. 7.65(c) shows the new node, and Fig. 7.65(d) shows the new heap, which has
one less element than the heap in Fig. 7.65(b).

Repeating the above step until the heap is empty, we obtain the required tree T in Fig. 7.65(c). We must
set ROOT = 15, since this is the location of the last node added to the tree.

Graphs: Representations and operations

There are two standard ways of maintaining a graph G in the memory of a computer. One way,
called the sequential representation of G, is by means of its adjacency matrix A. The other way,
called the linked representation of G, is by means of linked lists of neighbors.
Adjacency Matrix Suppose G is a simple directed graph with m nodes, and suppose the nodes of
G have been ordered and are called V1, V2...Vm. Then the adjacency matrix A = (a3) of the
graph G is the m x m matrix defined as follows:
aij = 1 if vi is adjacent to vj, that is, if there is an edge (vi,vj)
aij = 0 otherwise.
Such a matrix A, which contains entries of only 0 and 1, is called a bit matrix or a Boolean
matrix. The adjacency matrix A of the graph G does depend on the ordering of the nodes of G;
that is, a different ordering of the nodes may result in a different adjacency matrix. However, the
matrices resulting from two different orderings are closely related in that one can be obtained

[Link] [Link]
 Website: [Link]
from the other by simply interchanging rows and columns. Unless otherwise stated, we will
assume that the nodes of our graph G have a fixed ordering.
Suppose G is an undirected graph. Then the adjacency matrix A of G will be a symmetric matrix,
i.e., one in which a = a for every i and j. This follows from the fact that each undirected edge [u,
v] corresponds to the two directed edges (u, v) and (v, u). The above matrix representation of a
graph may be extended to multigraphs. Specifically, if G is a multigraph, then the adjacency
matrix of G is the m x m matrix A = (a) defined by setting a equal to the number of edges from
Vi to Vj.
Example 8.3 Consider the graph G in Fig. 8.3. Suppose the nodes are stored in memory in a
linear array DATA as follows:
DATA: X, Y, Z, W
Then we assume that the ordering of the nodes in G is as follows: V₁ = X, V2 = Y, V3 = Z and V4
= W. The adjacency matrix A of G is as follows:
0 0 0 1

1 0 1 1

1 0 0 1

0 0 1 0

Note that the number of 1's in A is equal to the number of edges in G.

Consider the powers A, A2, A³, ... of the adjacency matrix A of a graph G. Let ak(i, j) = the ij
entry in the matrix Ak.
Observe that a₁ (i, j) = aij gives the number of paths of length 1 from node vi to node vj. One can
show that a2(i, j) gives the number of paths of length 2 from vi to vj.
Path Matrix: Let G be a simple directed graph with m nodes, vi, 2. The path matrix or
reachability matrix of G is the m-square matrix P = (pij) defined as follows:
Pij=1 if there is a path from vi to vj. Pij= 0 otherwise.

[Link] [Link]
 Website: [Link]
Suppose, there is a path from Vi to Vj. Then there must be a simple path from Vi to Vj when Vi !=
Vj, or there must be a cycle from Vi to Vj when Vi = Vj. Since G has only m nodes, such a simple
path must have length m = 1 or less, or such a cycle must have length m or less. This means that
there is a nonzero ij entry in the matrix Bm, defined at the end of the preceding subsection.
Accordingly, we have the following relationship between the path matrix P and the adjacency
matrix A.
Proposition 8.3 Let A be the adjacency matrix and let P = (pij) be the path matrix of a digraph G.
Then P = 1 if and only if there is a nonzero number in the ij entry of the matrix
Bm = A +A2 + A3 + ...+ Am
Consider the graph G with m = 4 nodes in Fig. 8.3. Adding the matrices A, A2, A3 and A, we
obtain the following matrix B4, and, replacing the nonzero entries in-B4, by 1, we obtain the path
matrix P of the graph G:
B4 = P=
1 0 2 3 1 0 1 1
5 0 6 8 1 0 1 1
3 0 3 5 1 0 1 1
2 0 3 3 1 0 1 1

Examining the matrix P, we see that the node v2 is not reachable from any of the other nodes.
Recall that a directed graph G is said to be strongly connected if, for any pair of nodes u and v in
G, there are both a path from u to v and a path from v to u. Accordingly, G is strongly connected
if and only if the path matrix P of G has no zero entries. Thus the graph G in Fig. 8.3 is not
strongly connected.
Spanning trees
A spanning tree is a subset of Graph G, such that all the vertices are connected using minimum
possible number of edges. Hence, a spanning tree does not have cycles and a graph may have
more than one spanning tree.
Properties of a Spanning Tree:
 A Spanning tree does not exist for a disconnected graph.
 For a connected graph having N vertices then the number of edges in the spanning tree
for that graph will be N-1.
 A Spanning tree does not have any cycle.
 We can construct a spanning tree for a complete graph by removing E-N+1 edges,
where E is the number of Edges and N is the number of vertices.

[Link] [Link]
 Website: [Link]
 Cayley's Formula: It states that the number of spanning trees in a complete graph with
N vertices is NN−2NN−2
o For example: N=4, then maximum number of spanning tree possible
=44−244−2 = 16 (shown below ).
o

[Link] [Link]
 Website: [Link]
Minimum Spanning Tree(MST):
The weight of a spanning tree is determined by the sum of weight of all the edge involved in it.
A minimum spanning tree (MST) is defined as a spanning tree that has the minimum weight
among all the possible spanning trees.
Properties of Minimum Spanning Tree:
 A minimum spanning tree connects all the vertices in the graph, ensuring that there is a
path between any pair of nodes.
 An MST is acyclic, meaning it contains no cycles. This property ensures that it remains a
tree and not a graph with loops.
 An MST with V vertices (where V is the number of vertices in the original graph) will
have exactly V - 1 edges, where V is the number of vertices.
 An MST is optimal for minimizing the total edge weight, but it may not necessarily be
unique.
 The cut property states that if you take any cut (a partition of the vertices into two sets) in
the original graph and consider the minimum-weight edge that crosses the cut, that edge
is part of the MST.
Minimum Spanning Tree of a Graph may not be Unique: Like a spanning tree, there can also be
many possible MSTs for a graph as shown in the below image:

[Link] [Link]
 Website: [Link]
Shortest path
There are two main types of shortest path algorithms, single-source and all-pairs. Both types
have algorithms that perform best in their own way. All-pairs algorithms take longer to run
because of the added complexity. All shortest path algorithms return values that can be used to
find the shortest path, even if those return values vary in type or form from algorithm to
algorithm.
Single-source
Single-source shortest path algorithms operate under the following principle:
Given a graph G, with vertices V, edges E with weight function w(u,v)=wu,v, and a single source
vertex, s, return the shortest paths from s to all other vertices in V.
If the goal of the algorithm is to find the shortest path between only two given vertices, s and t,
then the algorithm can simply be stopped when that shortest path is found. Because there is no
way to decide which vertices to "finish" first, all algorithms that solve for the shortest path
between two given vertices have the same worst-case asymptotic complexity as single-source
shortest path algorithms.
This paradigm also works for the single-destination shortest path problem. By reversing all of
the edges in a graph, the single-destination problem can be reduced to the single-source problem.
So, given a destination vertex, t, this algorithm will find the shortest paths starting at all other
vertices and ending at t.
All-pairs: All-pairs shortest path algorithms follow this definition:
Given a graph G, with vertices V, edges E with weight function w(u,v) = wu,v return the shortest
path from u to v for all (u,v) in V.
The most common algorithm for the all-pairs problem is the floyd-warshall algorithm. This
algorithm returns a matrix of values M, where each cell Mi,j is the distance of the shortest path
from vertex i to vertex j. Path reconstruction is possible to find the actual path taken to achieve
that shortest path, but it is not part of the fundamental algorithm.
Dijkstra's Shortest Path Algorithm:
The graph has the following:
 vertices, or nodes, denoted in the algorithm by vv or uu;
 weighted edges that connect two nodes: (u,v) denotes an edge, and w(u,v) denotes its
weight. In the diagram , the weight for each edge is written in gray.

[Link] [Link]
 Website: [Link]

This is done by initializing three values:

 dist, an array of distances from the source node s to each node in the graph, initialized the
following way: dist(s) = 0; and for all other nodes v, dist(v) = ∞. This is done at the
beginning because as the algorithm proceeds, the dist from the source to each node v in
the graph will be recalculated and finalized when the shortest distance to v is found
 Q, a queue of all nodes in the graph. At the end of the algorithm's progress, Q will be
empty.
 S, an empty set, to indicate which nodes the algorithm has visited. At the end of the
algorithm's run, S will contain all the nodes of the graph.
The algorithm proceeds as follows:
1. While Q is not empty, pop the node v, that is not already in S, from Q with the
smallest dist (v). In the first run, source node s will be chosen because dist(s) was
initialized to 0. In the next run, the next node with the smallest dist value is chosen.
2. Add node v to S, to indicate that v has been visited
3. Update dist values of adjacent nodes of the current node v as follows: for each new
adjacent node u,
 if dist (v) + weight(u,v) < dist (u), there is a new minimal distance found for u, so
update dist (u) to the new minimal distance value;
 otherwise, no updates are made to dist (u).
The algorithm has visited all nodes in the graph and found the smallest distance to each
node. dist now contains the shortest path tree from source s.
Note: The weight of an edge (u,v) is taken from the value associated with (u,v) on the graph.
Bellman-Ford Algorithm:
Purpose:
Find the shortest paths from a single source vertex to all other vertices in a weighted graph.
It can handle negative edge weights (unlike Dijkstra’s), but cannot work correctly if the graph
contains a negative weight cycle reachable from the source.

[Link] [Link]
 Website: [Link]
Algorithm Steps
Input:
 Graph G(V, E) with vertices V, edges E
 Edge list form: (u, v, w)( where u is source vertex, v is destination vertex, and w is edge
weight
 Source vertex s
Output:
 Shortest distance from s to all vertices
 Detection of negative weight cycle (if any)
BellmanFord(V, E, source):
1. Initialize distance[] = ∞ for all vertices
2. distance[source] = 0
3. Repeat |V| - 1 times:
For each edge (u, v, w) in E:
If distance[u] + w < distance[v]:
distance[v] = distance[u] + w
4. For each edge (u, v, w) in E:
If distance[u] + w < distance[v]:
Print "Graph contains a negative weight cycle"
Stop
5. Return distance[]
Topological Sorting
Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that
for every directed edge u-v, vertex u comes before v in the ordering.
Note: Topological Sorting for a graph is not possible if the graph is not a DAG.
Here’s a step-by-step algorithm for topological sorting using Depth First Search (DFS):
 Create a graph with n vertices and m-directed edges.
 Initialize a stack and a visited array of size n.

[Link] [Link]
 Website: [Link]
 For each unvisited vertex in the graph, do the following:
o Call the DFS function with the vertex as the parameter.
o In the DFS function, mark the vertex as visited and recursively call the DFS
function for all unvisited neighbors of the vertex.
o Once all the neighbors have been visited, push the vertex onto the stack.
 After all, vertices have been visited, pop elements from the stack and append them to the
output list until the stack is empty.
 The resulting list is the topologically sorted order of the graph.
Time Complexity: O(V+E). The above algorithm is simply DFS with an extra stack. So time
complexity is the same as DFS.
Auxiliary space: O(V). due to creation of the stack.
Input: V = 6, edges = [[2, 3], [3, 1], [4, 0], [4, 1], [5, 0], [5, 2]]

\
Output: 5 4 2 3 1 0
Explanation: The first vertex in topological sorting is always a vertex with an in-degree of 0 (a
vertex with no incoming edges). A topological sorting of the following graph is "5 4 2 3 1 0".
There can be more than one topological sorting for a graph. Another topological sorting of the
following graph is "4 5 2 3 1 0".
Kahn's algorithm for Topological Sorting:
Algorithm:
 Add all nodes with in-degree 0 to a queue.
 While the queue is not empty:
o Remove a node from the queue.
o For each outgoing edge from the removed node, decrement the in-degree of the
destination node by 1.
o If the in-degree of a destination node becomes 0, add it to the queue.

[Link] [Link]
 Website: [Link]
 If the queue is empty and there are still nodes in the graph, the graph contains a cycle and
cannot be topologically sorted.
 The nodes in the queue represent the topological ordering of the graph.
Time Complexity: O(V+E). The outer for loop will be executed V number of times and the
inner for loop will be executed E number of times.
Auxiliary Space: O(V). The queue needs to store all the vertices of the graph.
Internal sorting
Algorithm 9.1: (Insertion Sort) INSERTION(A, N).
This algorithm sorts the array A with N elements.
1. Set A[0] := -∞. [Initializes sentinel element.]
2. Repeat Steps 3 to 5 for K = 2, 3, ..., N:
3. Set TEMP := A[K] and PTR := K - 1.
4. Repeat while TEMP < A[PTR]:
(a) Set A[PTR + 1] := A[PTR]. [Moves element forward.]
(b) Set PTR := PTR - 1.
[End of looр.].
5. Set A[PTR + 1] := TEMP. [Inserts element in proper place.]
[End of Step 2 loop.]
6. Return.
Example 9.4 Suppose an array A contains 8 elements as follows:
77, 33, 44, 11, 88, 22, 66, 55
Figure 9.3 illustrates the insertion sort algorithm. The circled element indicates the A[K] in each
pass of the algorithm, and the arrow indicates the proper place for inserting A[K].

[Link] [Link]
 Website: [Link]

Procedure 9.2: MIN(A, K, N, LOC)

An array A is in memory. This procedure finds the location LOC of the smallest element among
A[K], A[K + 1], ..., A[N].
1. Set MIN := A[K] and LOC := K. [Initializes pointers.]
2. Repeat for J = K + 1, K + 2, ..., N:
If MIN > A[J], then: Set MIN := A[J] and LOC := A[J] and LOC := J.
[End of loор.]
3. Return.
The selection sort algorithm can now be easily stated:

Algorithm 9.3: (Selection Sort) SELECTIÓN(A, N)

This algorithm sorts the array A with N elements.
1. Repeat Steps 2 and 3 for K = 1, 2, ..., N - 1:
2. Call MIN(A, K, N, LOC).
3. [Interchange A[K] and A[LOC].]
Set TEMP := A[K], A[K] := A[LOC] and A[LOC] := TEMP.
[End of Step 1 loop.]
4. Exit.

Example 9.5
Suppose an array A contains 8 elements as follows:
77, 33, 44, 11, 88, 22, 66, 55
Applying the selection sort algorithm to A yields the data in Fig. 9.4. Observe that LOC gives the
location of the smallest among A[K], A[K + 1],..., A[N] during Pass K. The circled elements
indicate the elements which are to be interchanged.

[Link] [Link]
 Website: [Link]
Solution:

[Link] [Link]