B2 BINARIES

+263 78 827 4002

ALGORITHMS AND DATA STRUCTURES
ALGORITHMS
-it is a step by step process of solving a problem.
-A set of instructions describing the steps followed in performing a specific task, for example, calculating change.
-Algorithms are not necessarily written in any specific language. Algorithms can be illustrated using the following:
Descriptions, Flowcharts, Pseudocodes, Structure diagrams.

Advantages of algorithms
- not biased towards any programming language
- easy to convert to a program code or flowchart
- easy to determine logic errors
- has finite steps which lead to a solution
Disadvantages
- time consuming to design, i.e. first convert to flowchart, then to program code
- most people find them difficult to learn

a. Descriptions: These are general statements that are followed in order to complete a specific task. They are not governed
by any programming language. An example is as follows:
Enter temperature in oC
Store the value in box C
Calculate the equivalent temperature in oF
Store the value in box F
Print the value of box C and F
End the program.

b. Pseudocodes:
- These are English-like statements, closer to programming language that indicate steps followed in performing a specific
task.
-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

VARIABLES
Definition: A variables is a memory location that can store a value that can change during program execution.
Naming variables: Each programming language has its own way of naming variables. However, the following conventions
are common:
- a variable should not be a reserved word. A reserved word is a word with a specific meaning / function in that
programming language, e.g. Print, else, are reserved words in BASIC
- Variables must start with an alphabetic character, not with digit.
- It is wise to name a variable using the data it stores, e.g. surname (to store surnames), DOB (to store a date of
birth), etc. Thus it must be meaningful to avoid confusion
- Must not be too long
- Must be one word

FROM TSAMBE STRUCTURE AND KAPONDENI .T

 B2 BINARIES
+263 78 827 4002
Control Structures in Pseudocode
A number of control structures are used in designing Pseudocodes. These includes: simple sequence, selection and iteration
(looping/repetition).

i. Simple sequence: This is whereby instructions are executed in the order they appear in a program without jumping any
one of them up to the end of the program. Statements are executed one after another in the order they are. It is simple and
avoids confusion. Example:
Enter first number, A
Enter second number, B
C=A+B
Print C
Stop
ii. Selection Structure:
This allows one to choose the route to follow in order to accomplish a specific task. Selection is written using the IF
....THEN...ELSE statement or the CASE statement.

IF...THEN ...ELSE statement: A programming structure that allows the user to choose one from at least two routes of
solving a problem. The following Pseudocodes compares two numbers entered through the keyboard and determines the
bigger one.
Enter first Number, A Enter first Number, A Enter first Number, A
Enter second number, B Enter second number, B
Enter second number, B
IF A>B THEN IF A > B THEN
Print A is bigger Print A is bigger IF A>B THEN Print A is bigger
ELSE ENDIF
IF A<B THEN Print B is bigger
IF A<B THEN IF A < B THEN
Print B is bigger Print B is bigger IF A=B THEN Print Numbers are equal
ELSE ENDIF
END
Print Numbers are equal IF A = B THEN
ENDIF Print Numbers are equal
ENDIF ENDIF
END END
The above 3 Pseudocodes produces the same result.

CASE Statement: This is an alternative to the IF...THEN...ELSE statement and is shorter. For example:
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

Iii. 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

FROM TSAMBE STRUCTURE AND KAPONDENI .T

 B2 BINARIES
+263 78 827 4002
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
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.
- 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.

c. While ... Do Statement: 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…END WHILE 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

FROM TSAMBE STRUCTURE AND KAPONDENI .T

 B2 BINARIES
+263 78 827 4002
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.

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

Repeat Until Loop While Endwhile Loop

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

c. Flowcharts
It is a diagram used to give details on how programs and procedures are executed. Flowcharts are drawn using specific
symbols, each with its own meaning, as given below:
Symbol Explanation
Process Symbol - Indicates where some form of processing occur

Arrow -Shows directional flow of data (data flow symbol)

Input /output - Parallelogram in shape. Indicates where data is entered and output form,
either screen display or printout.
Terminal - Oval in shape. Indicate the start and stop of a program. Therefore it is
written either Start/Begin/Stop/End.
Connector - Circular in shape. Denotes the start and end of a subroutine. Nothing
should be written inside it.
Pre-defined process Indicates a module/subprogram/procedure inside another program

Decision Represents a selection stage. Often used where a condition is, especially
in repetition and selection structures.

Illustrations of flowcharts for programs

1. Using Simple Sequence Structure
Start
Enter number, A
Enter number, B
Sum = A + B
Display Sum
Stop

Pseudocode for the flowchart on the left:

FROM TSAMBE STRUCTURE AND KAPONDENI .T

 B2 BINARIES
+263 78 827 4002
Flowchart equivalent to the pseudocode on the
right

2. Using Selection Structure

Flowchart Pseudocode equivalent

Enter first Number, A

Enter second number, B
IF A>B THEN
Print A is bigger
ELSE
IF A<B THEN
Print B is bigger
ELSE
Print Numbers are equal
ENDIF
ENDIF
END

3. Using Iteration
(a) Repeat ... Until Structure

FROM TSAMBE STRUCTURE AND KAPONDENI .T

 B2 BINARIES
+263 78 827 4002
Flowchart Pseudocode equivalent
Sum, Average, Count = 0
Repeat
Enter Number
Sum = Sum + Number
Count = count + 1
Until Count > 10
Average = Sum / count
Display Sum, count, Average
End

b) WHILE...WEND Structure and the FOR...TO...NEXT Loop

FROM TSAMBE STRUCTURE AND KAPONDENI .T

 B2 BINARIES
+263 78 827 4002
Flowchart Pseudocode equivalent
Sum, Average, Count = 0
WHILE Count <=10
Enter Number
Sum = Sum + Number
Count = count + 1
WEND
Average = Sum / count
Display Sum, count, Average
END

Illustration of control structures

Use of the Pre-defined Symbol and the connector

This is used when drawing flowcharts of subprograms as given below.
Start Module Accept Numbers
Enter First Number, A
Enter Second Number, B
Enter Third Number, C
End Module

c. Pseudocode for module Accept

Numbers

b. Flowchart for module Accept

Numbers
a. Flowchart for whole
program

Flowchart (a) above indicates modules named Accept Numbers, Add numbers Multiply Numbers and Display Results.
Flowcharts for individual modules can then be designed as given in diagram (b) above, only the first module is indicated.
Can you do the rest?

d. Structure Diagrams: These are diagrams that show relationships between different modules as given below.

FROM TSAMBE STRUCTURE AND KAPONDENI .T

 B2 BINARIES
+263 78 827 4002
Start
Sum, Product = 0
Enter First Number, A
Enter Second Number, B
Sum = A + B
Product = A * B
Display Sum, Product
End

The structure diagram above indicates five sub-programs of the program Process Numbers, namely Initialise, Accept
Numbers, Process Numbers, Display Results and Exit. The module Process Numbers has its own sub-programs, which are
Add Numbers and Multiply Numbers. Modules are appropriate for very large programs. Can you write pseudocode for
individual modules? The program can be written as a continuous single program as indicated on the right side of the
diagram.

DATA STRUCTURES
-it is a collection of different data items that are stored together as a single unit and the operstion allowable on
them.

-such data structures includes arrays, trees ,linked lists,stacks and queues.

- data structures can be static or dynamic.

FROM TSAMBE STRUCTURE AND KAPONDENI .T

 B2 BINARIES
+263 78 827 4002

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

• 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

FROM TSAMBE STRUCTURE AND KAPONDENI .T

 B2 BINARIES
+263 78 827 4002
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. Every array element is accessed or
referenced using an index (subscript), therefore uses index register addressing. It can either store
integers, or names, but not both in one unit.

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.

In Visual Basic, the number of elements stored in an array is N + 1, N being the number (subscript)
used when declaring the array.

Array index starts at Zero up to N, N being the number in the declaration of the array.

The index is also called Subscript, and therefore arrays are subscripted data types.

It is not possible to exceed the upper limit or go below the lower limit on the array index values. You will
receive a “Subscript out of range” error message if you try to do so.

In the above declaration, the array index starts from 0 to 4 and are integer values. The memory
locations will be as follows:

FROM TSAMBE STRUCTURE AND KAPONDENI .T

 B2 BINARIES
+263 78 827 4002
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) = “Kapondeni”

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:

FROM TSAMBE STRUCTURE AND KAPONDENI .T

 B2 BINARIES
+263 78 827 4002
Dim Names(4) As String
For i=0 to 4
Input Value
Names(i)=Value
Next i

One-dimensional arrays

A one-dimensional array is a data structure in which the array is declared using a single index and can be
visually represented as a list.

The following diagram shows the visual representation of the array Names(4):

0 Theresa
Lameck
1 Johanne

2 Laurence
Fadzai
3

Two-dimensional arrays

A two-dimensional array is a data structure in which the array is declared using two indices and can be
visually represented as a table.

Indices 0 1 2 3

0 Makombe Tinashe M 4A
Vheremu Alex M 4B
1
Mununi Mary F 3C
2 Chirongera Salpicio M 2C
Mutero Violet F 4C
3

The diagram above shows the visual representation of a 2 dimensional array Names(4,3)- 5 rows and 4
columns:

FROM TSAMBE STRUCTURE AND KAPONDENI .T

 B2 BINARIES
+263 78 827 4002
Each individual element can be referenced by its row and column indices. For example: Names(0,0) is
the data item “Makombe”

Names(2,1) is the item “Mary”

Names(1,2) is the item “M”

Initialising an array

Initialising an array is a procedure in which every value in the array is set with starting values – this
starting value would typically be “” for a string array, or 0 for a numeric array.

Initialisation is important to ensure that the array does not contain results from a previous use,
elsewhere in the program.

Algorithm for initialising a one-dimensional numeric array:

DIM TestScores(9) As Integer

DIM Index As Integer
FOR Index = 0 TO 9 TestScores(Index)
=0
NEXT Index

Algorithm for initialising a two-dimensional string array:

DIM Students(4,3) As String

DIM RowIndex, ColumnIndex As Integer
FOR RowIndex = 0 TO 4
FOR ColumnIndex = 0 TO 3
Students(RowIndex,ColumnIndex) = “” NEXT
ColumnIndex
NEXT RowIndex

Serial search on an array

The following pseudo-co de can be used to search an array to see if an item X exists:

01 DIM Index As Integer

02 DIM Flag As Boolean

FROM TSAMBE STRUCTURE AND KAPONDENI .T

 B2 BINARIES
+263 78 827 4002
03 Index = 0
04 Flag = False
05 Input X
06 REPEAT
07 IF TheArray(Index) = X THEN
08 Output Index
09 Flag = True 10 END IF
11 Index = Index + 1
12 UNTIL Flag = True OR Index > Maximum Size Of TheArray
13 IF Flag = False THEN
14 Show Message “Item not found”
15 END IF
Note that the variable Flag (line 04 and 09) is used to indicate when the item has been found and stop
the loop repeating unnecessarily (line 12 ends the loop if Flag has been set to True).

The Actual Visual Basic Code will be as follows:

Dim Index As Integer

Dim Flag As Boolean
Dim x As Integer
Index = 0
Flag =
False
x = InputBox("Enter item to Search")
Do
If Names(Index) = x Then
MsgBox (Names(Index) & " Has Been Found")
Flag = True
End If
Index = Index + 1
Loop Until (Flag = True Or Index > UBound(Names))
If Flag = False Then
MsgBox (x & " is not in the array")
End If

Sorting Array Elements

Dim y As Integer
Dim p As Integer

FROM TSAMBE STRUCTURE AND KAPONDENI .T

 B2 BINARIES
+263 78 827 4002
Dim z As Integer
For y = LBound(Names) To UBound(Names)
For p = LBound(Names) To UBound(Names) - 1
If Names(y) < Names(p) Then
z = Names(y)
Names(y) = Names(p)
Names(p) = z
End If
Next p
Next y

Deleting Array Elements

Dim i As Integer
For i = LBound(Names) To UBound(Names) - 1
Names(i) = Names(i + 1)
Next
' VB will convert this to 0 or to an empty string.
Names(UBound(Names)) = Empty

The above algorithm will shift elements of the array up (or left), removing the first element and then
completely removing the last element in the array.

The following is an alternative method of deleting an array element:

Dim Index As Integer

Dim Flag As Boolean
Dim x As Integer
Index = 0
Flag =
False
x = InputBox("Enter item to Search")
Do
If Names(Index) = x Then
MsgBox (Names(Index) & " Has Been Found")
Flag = True
Names(Index) = Empty
End If
Index = Index + 1

FROM TSAMBE STRUCTURE AND KAPONDENI .T

 B2 BINARIES
+263 78 827 4002
Loop Until (Flag = True Or Index > UBound(Names)) If
Flag = False Then
MsgBox (x & " is not in the array")
End If

The algorithm first searches the element to delete, and then remove it from the array.

NB:
• If the item is string, it replaces with empty spaces. However, if it is numeric, it replaces with a 0.
• Deleting form an array is often difficult as elements need to be shifted positions after deletion. It
is an effective method for deleting elements.

Dynamic Declaration of Arrays:

Arrays can also be declared dynamically so that the user has to decide the size of the array when the
program is running. The user does not need to specify the number of elements during the declaration
stage. Dynamic declaration of arrays is done as follows:

Dim Names( ) As String

Inside the module, one then needs to redefine the array as follows:

ReDim Names(5) As
String

This allows the user to create the array when he/she actually needs it, using a ReDim statement:
Dynamic arrays can be re-created at will, each time with a different number of items. When you
recreate a dynamic array, its contents are reset to 0 (or to an empty string) and you lose the data it
contains. If you want to resize an array without losing its contents, use the ReDim Preserve command:

ReDim Preserve Names(20) As String

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.

FROM TSAMBE STRUCTURE AND KAPONDENI .T

 B2 BINARIES
+263 78 827 4002

• 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:

- 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!!!!!!!!!!!

FROM TSAMBE STRUCTURE AND KAPONDENI .T

 B2 BINARIES
+263 78 827 4002

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

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

FROM TSAMBE STRUCTURE AND KAPONDENI .T

 B2 BINARIES
+263 78 827 4002
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

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-

FROM TSAMBE STRUCTURE AND KAPONDENI .T

 B2 BINARIES
+263 78 827 4002
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

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

FROM TSAMBE STRUCTURE AND KAPONDENI .T

 B2 BINARIES
+263 78 827 4002
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.
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

FROM TSAMBE STRUCTURE AND KAPONDENI .T

 B2 BINARIES
+263 78 827 4002
*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
• 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:

FROM TSAMBE STRUCTURE AND KAPONDENI .T

 B2 BINARIES
+263 78 827 4002

IMPLEMENTATION OF BINARY TREES USING ARRAYS

Binary trees can be implemented using left and right pointers for each node. Each node will have the
following:

- Left pointer
- Right pointer
- Data item
Let’s take the binary tree below:

These can be illustrated as follows:

Left Data Right

Tree [1] 2 Long 5
Tree [2] 0 Charlesworth 3

FROM TSAMBE STRUCTURE AND KAPONDENI .T

 B2 BINARIES
+263 78 827 4002
Tree [3] 4 Illman 7
Tree [4] 0 Hawthorne 0
Tree [5] 8 Todd 6
Tree [6] 0 Youngman 0
Tree [7] 0 Jones 0
Tree [8] 0 Ravage 0
- The pointer value 0 indicates a ‘nil’ pointer, thus a node will be pointing to nothing. -
Tree[1].Left = 2
- Tree[Tree[1].Left].Right = 3
- Tree[6].Data = “Youngman”

YOUR VOTES MATTERS!!!

B2 BINARIES

FROM TSAMBE STRUCTURE AND KAPONDENI .T