ALGORITHM DESIGN AND DATA STRUCTURES

ALGORITHMS
- A set of instructions describing the steps followed in performing a specific task, for
example, calculating change.
- They are a sequence of instructions for solving a problem.
- Algorithms can be illustrated using the following:
Descriptions, Flowcharts, Pseudocodes, Structure diagrams
Pseudocodes:
- These are English-like statements, closer to programming language that indicates steps
followed in performing a specific task.
- They are means of expressing algorithms without worrying about the syntax of the
programming language.
- There are no strict rules on how pseudocode statements should be written.
- Indentations are very important in writing pseudocodes since they clearly indicate the
extent of loops and conditional statements.
- They are however independent of any programming language.
- An example is as follows:
Enter centigrade temperature, C
If C = 0, then stop.
Set F to 32 + (9C/5)
Print C and F
End
Control Structures/Programming Constructs/building blocks of a structured program
- A number of control structures are used in designing Pseudocodes.
- These includes: simple sequence, selection and iteration.
NB: GO TO statements (also called spaghetti programming) must be avoided as the programs
will be difficult to follow, difficult to debug, and difficult to maintain.

Selection and Repetition Constructs

In programming, constructs are structures that control how a program runs.
1. Selection Constructs (Making Decisions)

17
 ALGORITHM DESIGN AND DATA STRUCTURES

A Selection construct allows a program to choose between different paths based on whether a
condition is True or False. It is just like making a decision in real life.
The IF...THEN...ELSE Statement
This is the most common selection tool.
 Scenario: Think of a grading system for a Form 5 test.
 Logic: IF a student gets 50% or more, THEN they pass. ELSE, they fail.
Real-World Zimbabwe Example: EcoCash
When you dial *151# to use EcoCash, the system uses selection:
 IF your PIN is correct, THEN show the menu.
 ELSE, show an error message saying "Invalid PIN."
� Example:
IF mark >= 50 THEN
DISPLAY "Pass"
ELSE
DISPLAY "Fail"
ENDIF
Cascaded/Nested If Statements
This is whereby if statements are found inside other if statements (nested Ifs) as shown below:
Start
Enter “First Number”, A
Enter “Second Number”, B
Enter “Third Number”, C
If A>B Then
If B>C Then
Print “A is the biggest Number”
End If
End If
End.
CASE Statement: This is an alternative to the IF...THEN...ELSE statement and is shorter. For
example:
START

18
 ALGORITHM DESIGN AND DATA STRUCTURES

Enter first Number, A

Enter second number, B
Enter operand (+, -, * /)
CASE operand of:
“+”: C = A + B
“-”: C = A-B
“*”: C = A*B
“/”: C = A/B
ENDCASE
Print C
END
i. Repetition/Iteration/looping:
A control structure that repeatedly executes part of a program or the whole program until a
certain condition is satisfied.
Iteration is in the following forms: FOR...NEXT LOOP, REPEAT... UNTIL Loop and the
WHILE...ENDWHILE Loop.
a. For...Next Loop: A looping structure that repeatedly executes the loop body for a specified
number of times. The syntax of the For...Next loop is as follows:
FOR {variable} = {starting value} to {ending value} DO
Statement 1
Statement 2 loop body
................
NEXT {variable}

A group of statements between the looping structures is called the loop body and is the one that
is repeatedly executed.
The For...Next loop is appropriate when the number of repetitions is known well in advance, e.g.
five times. An example of a program that uses the For...Next loop is as follows:
Sum, Average = 0
FOR I = 1 to 5 DO
Enter Number

19
 ALGORITHM DESIGN AND DATA STRUCTURES

Sum = Sum + number

NEXT I
Average = Sum/5
Display Sum, Average
End

b. Repeat...Until Structure: This is a looping structure that repeatedly executes the loop body
when the condition set is FALSE until it becomes TRUE. The number of repetitions may not be
known in advance and the loop body is executed at least once. The syntax is as follows:
Repeat
Statement 1
Statement 2 loop body
................
Until {Condition}
For example
Sum, Average, Count = 0
Repeat
Enter Number (999 to end)
Sum = Sum + Number
Count = count + 1
Until Number = 999
Average = Sum / count
Print Sum, count, Average
End
In the above program:
- Count records the number of times the loop body executes.
- 999 is used to stop further data entry through the keyboard and thereby ending the loop.
Such a value that stops further data entry through the keyboard thereby terminating a loop
is called a Rogue value or sentinel.

20
 ALGORITHM DESIGN AND DATA STRUCTURES

- The condition here is {Number = 999}. The loop exits when the number 999 is entered.
If 999 is part of the number to be entered in this program, then the user has to split it into
two numbers, that is 999 = 990 + 9, therefore can be entered separately as 990 and 9.
- A flag is also used to control the loop. In this case 999 is also a flag.
NB. As for the Repeat...Until loop, the condition is tested after the loop body has been run at
least once, even when the condition is true from start. This is rather misleading.
b. While ... Do Structure
A looping structure in which the loop body is repeatedly executed when the condition set is
TRUE until it becomes FALSE. It is used when the number of repetitions is not known in
advance. The condition set is tested first before execution of the loop body. Therefore the loop
body may not be executed at all if the condition set is FALSE from start. The syntax of the
WHILE…ENDWHILE structure is as follows:
WHILE {condition}
Statement 1
Statement 2 loop body
................
ENDWHILE
An example of the program is as follows:
Sum, Count, Average = 0
WHILE Count < 6 DO
Enter Number
Sum = Sum + number
Count = count + 1
ENDWHILE
Average = Sum/count
Display sum, count, average
END
The word WEND can be used to replace the word ENDWHILE in some structures and
therefore is acceptable. The word Do, after the condition is optional.

21
 ALGORITHM DESIGN AND DATA STRUCTURES

Differences between the Repeat...Until and the While…ENDWHILE structures

Repeat Until Loop While End while Loop

1 Loop body is executed when the Loop body is executed when the condition
condition set is FALSE until it set is TRUE until it becomes FALSE
becomes TRUE
2 Loop body is executed at least once Loop body may not be executed at all
3 Condition is tested well after Condition is tested before execution of loop
execution of loop body body

SORTING ALGORITHMS
Bubble sort
 Sorting whereby the array is scanned from right to left multiple times (passes) until all
elements are in their correct positions
 Compare each element with the adjacent, and if it is greater than the next element then swap
the elements.
For k = 0 to N – 1 {counts the number of passes / scans made to the array}
For i = 0 to N – 2 {use N – 2 instead of N – 1 so that at the end of the array you will be able to
compare Array[i] and Array[i+1]}
If Array[i] > Array[i+1] Then {compare adjacent elements}
Swap(Array[i], Array[i+1]) {swapping element, i.e Array[i] = [i+1]}
End if
Next i
Next k
Example
Arrange the following numbers in ascending order using the bubble sort algorithm
17 18 2 11 0
[0] [1] [2] [3] [4]

1. - compare Array [0] with Array[1] {no swap}

- Compare Array [1] with Array[2] {swap}

22
 ALGORITHM DESIGN AND DATA STRUCTURES

- Compare Array [2] with Array [3] {swap}

- Compare Array [3] with Array [4] {swap}
 Therefore after the first pass the array will be like this
17 2 11 0 18
2. – compare Array [0] with Array[1] {swap}
- Compare Array [1] with Array[2] {swap}
- Compare Array [2] with Array [3] {swap}
- Compare Array [3] with Array [4] {no swap}
 After the 2nd pass
2 11 0 17 18
3. – compare Array [0] with Array[1] {no swap}
- Compare Array [1] with Array[2] {swap}
- Compare Array [2] with Array [3] {no swap}
- Compare Array [3] with Array [4] {no swap}
 After the 3rd pass
2 0 11 17 18
4. – compare Array [0] with Array[1] {swap}
- Compare Array [1] with Array[2] {no swap}
- Compare Array [2] with Array [3] {no swap}
- Compare Array [3] with Array [4] {no swap}
 After the 4th pass i.e k = N-1
0 2 11 17 18

The bubble sort standard algorithm in pseudocode

For Pass = 0 to MaxIndex – 1
For j = 0 to MaxIndex – 1
If Data(j) > Data(j + 1) Then
Temp = Data(j)
Data(j) = Data(j + 1)
Data(j + 1) = Temp
End if

23
 ALGORITHM DESIGN AND DATA STRUCTURES

Next j
Next pass

Examine the following table. (Note that each pass represents the status of the array after the
completion of the inner for loop, except for pass 0, which represents the array as it was passed to
the function for sorting)
8 6 10 3 1 2 5 4 } pass 0
6 8 3 1 2 5 4 10 } pass 1
6 3 1 2 5 4 8 10 } pass 2
3 1 2 5 4 6 8 10 } pass 3
1 2 3 5 4 6 8 10 } pass 4
1 2 3 4 5 6 8 10 } pass 5
1 2 3 4 5 6 8 10 } pass 6
1 2 3 4 5 6 8 10 } pass 7
The above tabulated data clearly depicts how bubble sort works. Note that each pass results in
one number being bubbled to the end of the list.

24
 ALGORITHM DESIGN AND DATA STRUCTURES

Trace table for a bubble sort.

Basing on the bubble sort pseudocode given earlier, produce a trace table when the following list,

Pass j Temp Data(j) Data(j+1) Swapping process

Temp = Data(j) = Data(j+1) = Temp
Data(j) Data(j+1)
1 0 6 9
1 9 7 9 7 9
2 9 9 3 9 3 9
Status of the array after pass 1, note the shaded numbers
6 7 3 9 Moving on to pass 2
2 0 6 7
1 7 3 7 3 7
2 7 9
Status of the array after pass 2, note the shaded numbers
6 3 7 9 Moving on to pass 3
3 0 6 3 6 3 6
1 6 7
2 7 9
Status of the array after pass 3, note the shaded numbers
3 6 7 9
6 9 7 3 is required to be sorted in ascending order

25
 ALGORITHM DESIGN AND DATA STRUCTURES

The bubble sort standard algorithm can be modified or optimised to improve its efficiency as
shown below. The test data is 6 9 7 3
Identifier Explanation
Data[0…3] One-dimension array to store 4 numbers
MaxIndex The last index number of array elements
n The number of elements to compare in each pass
Pass Control variable for outer loop
j Control variable for inner loop
Temp Variable for temporary storage while swapping array elements

n = MaxIndex – 1
For Pass = 0 to MaxIndex – 1
For j = 0 to n
If Data(j) > Data(j+1)
Temp = Data(j)
Data(j) = Data(j + 1)
Data(j + 1) = Temp
End if
Next j
n = n – 1 // this restricts the algorithm to deal only with array elements not in
// correct positions in the inner loop
Next pass
Note: the effect of the statement n = n – 1 in the algorithm. The statement restricts the algorithm
from performing comparison on array elements which are already in the correct position. The
inner loop control variable c, iterates from 1 to 3 in the first pass, pass 1. In pass 2, the inner loop
terminates when c = 1. The idea here is to avoid CPU overheads and increase throughput.

26
 ALGORITHM DESIGN AND DATA STRUCTURES

6 9 7 3
The trace table
Pass j Temp Data(j) Data(j+1) Swapping process
Temp=Data(j) Data(j)=Data(j+1) Data(j+1)=Temp
1 0 6 9
1 9 7 9 7 9
2 9 3 9 3 9
Status of the array after pass 1, note the shaded numbers
6 7 3 9 Moving on to pass 2
2 0 6 7
1 7 3 7 3 7
Status of the array after pass 2, note the shaded numbers
6 3 7 9 Moving on to pass 3
3 0 6 3 6 3 6
Status of the array after pass 3, note the shaded numbers
3 6 7 9

Quick Sort
7 2 1 6 8 5 3 4 5

 A very fast method of sorting elements in an array

 Involves splitting an array into two sub lists, then quicksort each sub list by splitting them
into two sub list and quicksort each….. recursively
 Quicksort involves recursively calling the process of partitioning (splitting) an array
 Partitioning is the process of selecting a pivot and rearranging elements in such a way that
elements greater than the pivot are to the right of the pivot and those less than the pivot are to
the left thus you have two sub lists.
 Repeat the process until all elements are sorted.
Lets us go through this example
7 2 1 6 8 5 3 4

27
 ALGORITHM DESIGN AND DATA STRUCTURES

First select a pivot (select any one of the elements and move it to the end of the array) say 5
Now to rearrange the elements we need to make swaps so that elements less than the pivot are to
the left and those greater are to the right. - Swap element from left which is greater than the pivot
with element from the right which is smaller than the pivot, repeat the process until element from
left is greater than the pivot, then swap the element with the pivot
7 2 1 6 8 3 4 5

4 2 1 6 8 3 7 5

4 2 1 3 8 6 7 5

4 2 1 3 5 6 7 8
Sub list 1 – elements < pivot

Now repeat the process for each sub list

Let’s take sub list 1
4 2 1 3
 Select pivot, say 2 and move it to the end of the list
4 1 3 2
 Now to rearrange the elements we need to make swaps so that elements less than the
pivot are to the left and those greater are to the right.
 Swap element from left which is greater than the pivot with element from the right which
is smaller than the pivot, repeat the process until element from left is greater than the
pivot, then swap the element with the pivot

28
 ALGORITHM DESIGN AND DATA STRUCTURES

4 1 3 2

1 4 3 2

1 2 3 4

 Now we have a sorted sub list, do the same for the other sub list
Then will have a sorted array
1 2 3 4 5 6 7 8
Another example
 The elements below need to be sorted in ascending order
(28) 49 14 51 40 13 19
 Let 28 be reference number denoted by brackets since it is first number in the list
 We set two pointers: one at each end of the list
(28) 49 14 51 40 13 19

 Compare the two numbers with pointers

 28 > 19, therefore swap and move left pointer to 49
19 49 14 51 40 13 (28)

 Compare the two numbers with pointers

 28 < 49, therefore swap and move right pointer to 13
19 (28) 14 51 40 13 49

 Compare the two numbers with pointers

 28 > 13, therefore swap and move left pointer to 14

29
 ALGORITHM DESIGN AND DATA STRUCTURES

19 13 14 51 40 (28) 49

 Compare the two numbers with pointers

 28 > 14, therefore no swap and move left pointer to 51
19 13 14 51 40 (28) 49

 Compare the two numbers with pointers

 28 < 51, therefore swap and move right pointer to 40
19 13 14 (28) 40 51 49

 Compare the two numbers with pointers

 28 < 40, therefore no swap and move right pointer to 28
19 13 14 (28) 40 51 49

The two pointers are now at the same position and the pivot, 28, has been placed at its rightful
position, where elements to the right of it are greater while those on the left are smaller. We now
create two sub list or array that exclude the pivot (28), the left sub-list and the right sub-list as
shown below
19 13 14 (28) 40 51 49

Left Sub-list Right Sub-list

Perform quick sort on these sub-list separately

19 13 14

 Let 14 be reference number denoted by brackets

 We set two pointers: one at each end of the list
30
 ALGORITHM DESIGN AND DATA STRUCTURES

19 13 (14)

 Compare the two numbers with pointers

 19 > 14, therefore swap and move right pointer to 13
(14) 13 19

 Compare the two numbers with pointers

 14 > 13, therefore swap and move right pointer to 14
13 (14) 19

The two pointers are now at the same position and the pivot
40 51 49
 Let 49 be reference number denoted by brackets
 We set two pointers: one at each end of the list
40 51 (49)

 Compare the two numbers with pointers

 40 < 49, therefore no swap and move left pointer to 51
40 51 (49)

 Compare the two numbers with pointers

 51 > 49, therefore swap and move right pointer to 49
40 49 51

The two pointers are now at the same position and the pivot
Then will have a sorted array
13 14 19 28 40 49 51

31
 ALGORITHM DESIGN AND DATA STRUCTURES

Insertion
 Items are copied from unsorted array to a new sorted array
 Each element is inserted into the right place so that the output array is always sorted
 Considerably faster than bubble sort but slower than quick sort
Searching Algorithms
a) Linear search
- searching data items one by one until item is found or end of list reached
- this involves comparing each item in the list with the item sought for match, if match
then item found
Start at the beginning of list
Repeat
Test next item for a match
Until item found or end of list reached

b) Binary Search
- Search through an ordered array and is much faster than linear search.
- Divides the array into 3 parts: middle item, lower part and upper part
- The middle item is compared with the item sought for match, if they match them item
found.
- If middle item is less than item sought (middle < itemsought), then the lower half of
the array is discarded, it will be of no interest.
- Therefore, the number of items search is reduced by half, repeat the process until the
last item is examined, with either the upper half or lower half of the items searched
being discarded at each pass.
BinarySearch (Low, Top, ItemSought)
Low = 0
Top = n – 1 {n = number of items in the array}
While low <=Upper
Mid = (Low + Top)/2
If A[Mid] = ItemSought Then {compare middle with ItemSought, if equal them
search found}

32
 ALGORITHM DESIGN AND DATA STRUCTURES

Search found = True

Else If ItemSought < A[Mid] Then
Top = Mid – 1 {Discard upper half, if ItemSought is less than middle}
Else
Low = Mid + 1 {Discard lower half if ItemSought is greater than middle}
Endif
End While
Example:
Given an array of integers 2,4,6,7,11,13,19,21,27,29. Use Binary search to search for 19
in the array.
Solution:
2 4 6 7 11 13 19 21 27 29
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9)
Low = 0
Top = 10 -1 = 9
ItemSought = 19
Mid = (0+9)/2 = 4,5 = 5 {round off to get the whole number part}
2 4 6 7 11 13 19 21 27 29
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
- Compare the item at index 5 with ItemSought (13 and 19)
- Mid (13) is less than ItemSought (19), therefore discard the lower half,
- low becomes 6 (mid +1) and
19 21 27 29 Top remains
[6] [7] [8] [9]

Mid = (6+9)/2 = 7,5 = 8 {round off to get the whole number part}

19 21 27 29
[6] [7] [8] [9]
-
- Compare the item at index 8 with ItemSought (27 and 19)
- Mid (27) is greater than ItemSought (19), therefore discard the upper half,

33
 ALGORITHM DESIGN AND DATA STRUCTURES

- low remains 6 and Top becomes 7 (mid -1)

19 21
[6] [7]

Mid = (6+7)/2 = 6,5 = 7 {round off to get the whole number part}

19 21
[6] [7]

- Compare the item at index 7 with ItemSought (21 and 19)

- Mid (21) is greater than ItemSought (19), therefore discard the upper half,
- low remains 6 and Top becomes 6 (mid -1)
19
[6]

Mid = (6+6)/2 = 6
- Compare the item at index 6 with ItemSought (19 and 19), Mid = ItemSought
therefore item found
Trace Table
Low Top Mid Found
0 9 5 False
6 9 8 False
6 7 7 False
6 6 6 True

34
 ALGORITHM DESIGN AND DATA STRUCTURES

DATA STRUCTURES
A data structure is a collection of different data items that are stored together as a single unit and
the operations allowable on them. Such data structures includes arrays, trees, linked lists, stacks
and queues. Data structures can be static or dynamic.
Static data structure
 Are those which do not change in size while the program is running, e.g arrays and fixed
length records.
 Most arrays are static, i.e., once you declare them, they cannot change in size.
 It main advantage is that amount of storage is known and therefore is easier to program
Advantages of Static Data Structures
 Easy to check for overflow
 Memory allocation is fixed and therefore there is no problem with adding and removing
data items.
 Compiler can allocate space during compilation
 Easy to program as there is no need to check for data structure size at any given
time/point
 An array allows random access and is faster to access elements than in other data
structures
Disadvantages of Static Data Structures
 Programmer has to estimate maximum amount of space needed, which may be difficult
 Can waste a lot of space if some space is left with no data entered into it.
 Adding, removing and modifying elements is not directly possible. If done, it requires a
lot of resources like memory.
DYNAMIC DATA STRUCTURES
 Can increase and decrease in size while the program is running, e.g. binary trees, linked
lists, etc.
 they uses the space needed at any time, no limitations at all, unless computer memory is
full
 its size changes as data is added & removed (size is not fixed)
Advantages of Dynamic Data Structures
 Only uses the space that is needed at any time
35
 ALGORITHM DESIGN AND DATA STRUCTURES

 Makes efficient use of the memory, no spaces lie idle at any given point
 Storage no-longer required can be returned to the system for other uses.
 Does not allow overflow
 There is effective use of resources as resources are allocated at run-time, as they are
required.
Disadvantages of Dynamic Data Structures
 Complex and more difficult to program as software needs to keep track of its size and
data item locations at all times
 Can be slow to implement searches
 A linked list only allows serial access
Static data structure
Array
An array is a static data structure, which stores and implements a set of items of the same data
type using the same identifier name, in contiguous memory location.
Declaration of arrays using VB 6.0
Arrays are declared by stating the following parameters: array name, array size, dimensions and
the data type. The size of the array is the maximum number of elements that it can store. For
example, the following declares an array that reserves five locations in memory and labels these
as ‘Names’:
Dim Names(4) As String
This can also be declared as
Dim Names(0 to 4 ) As String
One may also declare the array as
Dim Names(1 to 5) As String
The last option modifies the starting value and the ending value of the indices, but the number of
elements still remains the same.
By default, this implies that the array stores at most 5 elements. On running, the computer creates
5 contiguous memory locations under the name “Names”. Thus Names will contain 5 partitions.
Each memory partition will be accessed using an index, which is the address of the memory space
in the array.

36
 ALGORITHM DESIGN AND DATA STRUCTURES

Names[0] Names[1] Names[2] Names[3] Names[4]

The five individual locations are Names (0), Names (1), Names (2), Names (3) and Names (4).
Each data item is called an element of the array. To reference a particular element one must use
the appropriate index.
NB: However, most programming languages differ with Microsoft Visual basic in handling
arrays, especially on the amount of memory allocated. For example, using Java, the
following declaration:
Int [4 ]Names;
This array declaration creates exactly 4 memory spaces for the array Names. The indices of
the array range from 0 to 3 which are
Names[0], Names[1], Names[2] and Names[3]
Initialising an array in Visual Basic 6.0
The procedure of initializing an array in the computer memory is as follows:
- Size of array is calculated
- Location of array is decided according to data type and size
- Locations are reserved for the array
- Size of array is stored in a table
- Lower bound of the array is stored in a table
- Upper bound of array is stored in a table
- Data type is stored in a table
- Address of first element is stored in a table
Inserting data into an array
One may use the assignment statement or use looping structures. For example, the following
statement assigns data to the 4th element:
Names(3) = “Manyeruke”
Arrays simplify the processing of similar data. An algorithm for getting four names from the user
and storing them in the array Names is shown below:
Dim Names(4) As String
For i=0 to 4

37
 ALGORITHM DESIGN AND DATA STRUCTURES

Input Value
Names(i)=Value
Next i
DYNAMIC DATA STRUCTURE
Binary Trees
A binary tree is a data structure, consisting of a root node and zero, one or two sub-tree which
are organised in a hierarchical way. Each node is a parent of at most two nodes.

-
 The data items are held in nodes.
 The possible routes are called paths/branches. They are lines connecting the nodes.
 Each node has two possible paths.
 The nodes are arranged in layers.
 The first node is called the root, or root node. Each tree has only one root node.
However, each branch can have its branch root.
 Node created by another one is called child node (children)
 Each child node has only one parent node
 Each parent node has at most two children
 The last node is called the leaf node/terminal node (has no children)
 Nodes that share common parent are called siblings

For example, given the following numbers: 20, 30, 5, 2, 7, 6, 17, 58, 41
Placing them in the binary tree is as follows:

38
 ALGORITHM DESIGN AND DATA STRUCTURES

- The first element becomes the root node, i.e. 20

- For other numbers, the bigger number goes to the right and the smaller one to the right of
a node. Every time start from the root node, until you get to an empty space to place the
new node.
- For example, 30, is bigger than 20, therefore is placed to the right hand side of 20. There
is nothing on this side and therefore a new node is created and 30 placed inside.
- Next is 5, which is smaller than 20 (root node) and therefore goes to the left. There is an
empty space therefore a new node is created and 5 is placed inside.
- Then 2 is smaller than 20 (root node) and therefore goes to the left. On the left there is 5.
2 is smaller than 5, therefore we go to the left and place 2 there.
- Next is 7, which is smaller than 20, we go to the left where there is 5. Seven (7) is bigger
than 5, therefore we place it to the right of 5.
- ……….finish on your own!!!!!!!!!!!

Algorithm for constructing a binary tree.

Place first item into root node
For subsequent items, start from root node
Repeat
If (new item > this node item) Then
Follow right pointer
Else
Follow left pointer
Endif
Until pointer =0
Place item at this node

39
 ALGORITHM DESIGN AND DATA STRUCTURES

Binary tree traversal

Tree traversal refers to means of walking through the tress structure such that each node is
visited once. Traversal of trees is a recursive function-they call themselves. Common traversal
methods are: Pre-Order, In-order and Post-Order Traversals.
A. Pre-Order traversal
The order of traversal is:
- Visit the Node
- Traverse the Left sub-tree
- Traverse the Right sub-tree.
This is generally given as NLR
For the diagram above, the pre-order traversal will be as follows:
20, 5, 2, 7, 6, 17, 30, 58, 41.
The algorithm for pre-order traversal is as follows:
1. Print current node
2. For the current node, check if there is left sub-tree
3. If there is left sub-tree, go to the root node of this sub-tree and print it
4. For the current node, check if there is right sub-tree
5. If right sub-tree is present, then go to 6, else go to 7
6. Repeat 1
7. End
Recursive Algorithm for pre-order traversal
Procedure traversefrom(p)
Print (data);
If Tree[p].Left<>0 Then
Traversefrom(Left)
EndIf
If Tree(p).Right <> 0 Then
traversefrom(Right)
endif
endProcedure

40
 ALGORITHM DESIGN AND DATA STRUCTURES

B. In-Order Traversal
The order of traversal is:
- Traverse the Left sub-tree
- Visit the Node
- Traverse the Right sub-tree.
This is generally given as LNR
For the diagram above, the pre-order traversal will be as follows:
2, 5, 6, 7, 17, 20, 30, 41, 58.
NB: In-order traversal prints items in ascending order or in alphabetical order if they are
alphabetic items.
In-order traversal algorithm:
1. For the current node, check if there is left-sb-tree. If it exists, go to the root node of this
sub-tree and then go to 2. If it doesn’t exist, go to 3.
2. Repeat 1
3. Print the current node
4. For the current node. Check whether it has a right sub-tree. If it has, go to 5. Else go to 6
5. Repeat 1
6. End

Recursive Algorithm for in-order traversal

Procedure traversefrom(p)
If Tree[p].Left<>0 Then
Traversefrom(Left)
EndIf
Print (data);
If Tree(p).Right <> 0 Then
traversefrom(Right)
endif
endProcedure

41
 ALGORITHM DESIGN AND DATA STRUCTURES

C. Post-Order Traversal
The order of traversal is:
- Traverse the Left sub-tree
- Traverse the Right sub-tree.
- Visit the Node

This is generally given as LRN

For the diagram above, the pre-order traversal will be as follows:
2, 6, 17, 7, 5, 41, 58, 30, 20.

The algorithm for post-order traversal is as follows:

Procedure traversefrom(p)
If Tree[p].Left<>0 Then
Traversefrom(Left)
EndIf
If Tree(p).Right <> 0 Then
traversefrom(Right)
endif
Print (data);
endProcedure
Inserting Data into a Binary Tree
 Look at each node starting from the root node
 If the root is empty, create the node and place the value
 If the new value is less than the value of the of the node, move left, other wise move right
 Repeat this for each node arrived until there is no node
 Then create a new node and insert the data.
 Perform until no new item need to be added
This can be written algorithmically as:
1. If tree is empty, enter data item at root and stop.
2. Current node = root.
3. Repeat steps 4 and 5 until current node is null.

42
 ALGORITHM DESIGN AND DATA STRUCTURES

4. If new data item is less than value at current node go left else go right.
5. Current node = node reached (null if no node).
6. if node reached is null, create new node and enter data.
This can also be written as:
Repeat
Compare new value with root value
If new value > root value then
Follow right sub-tree
Else
Follow left sub-tree
Endif
Until no sub-tree
Insert new value as root of new sub-tree.

Deleting Data from a Tree

Deleting data from a tree is quite complicated, because if it has sub-nodes, these will also be
deleted. There are two options however:
1. The structure could be left the same, but the value of that node set to deleted.
2. The tree could be traversed, the values removed, put into a stack and then put back into a
binary tree.
Problems when deleting element from tree and solution
 The value at the node is not only data, it is part of the structure of the tree
 If the node is simply deleted then the sub-tree leading from it is not navigable
*NB: the algorithm to delete a leaf node is straightforward as deleting a leaf node does not
change the structure of the tree
To remove the value from the tree, either:
 It remains in the tree structure
 Mark value as deleted so that it cannot be output but acts as the root for its sub-tree
OR:
 The entire sub-tree without its root is read to a list
 The sub-tree is deleted

43
 ALGORITHM DESIGN AND DATA STRUCTURES

 The values in the list are read back into the tree (element which was originally on the left
will replace the deleted element (becomes root of that branch))
Searching item from Binary Tree
The algorithm is as follows:
Enter item to search(this item)
Start at root node
Repeat
If wanted item = this item Then
Found = True
Display Item
Else
If wanted Item >this item Then
Follow right pointer
Else
Follow left pointer
EndIf
EndIf
Until (Found=True or Null pointer is encountered)

Binary tree maintain the order of elements. However, if one element is deleted, the order is
affected.
In some cases, each node (data) may be assigned pointers (right and left pointer). This is as
illustrated below:

44