# Tracing BST Pseudocode for Insertion

I'm having real trouble tracing some pseudocode for insetion into a Binary Search Tree. I need to understand this in order to be able to teach it, but I think there are flaws in the material.

For example,

CALL FindInsertionPoint(NewDataItem, Index, Direction)

is only meant to have one parameter according to the description in the question, and should return Index and Direction:

Doesn't this make the line before it in the code below:

Index ← RootPointer

redundant?

PROCEDURE AddToTree(BYVALUE NewDataItem : STRING)
// if no free node report an error
IF FreePointer = -1
THEN
OUTPUT("No free space left")
ELSE // add new data item to first node in the free list
NewNodePointer ← FreePointer
Tree[NewNodePointer].Data ← NewDataItem
FreePointer ← Tree[FreePointer].LeftPointer
// clear left pointer
Tree[NewNodePointer].LeftPointer ← -1
// is tree currently empty ?
IF RootPointer = -1
THEN // make new node the root node
RootPointer ← NewNodePointer
ELSE // find position where new node is to be added
Index ← RootPointer
CALL FindInsertionPoint(NewDataItem, Index, Direction)
IF Direction = "Left"
THEN // add new node on left
Tree[Index].LeftPointer ← NewNodePointer
ELSE // add new node on right
Tree[Index].RightPointer ← NewNodePointer
ENDIF
ENDIF
ENDIF
ENDPROCEDURE


I've tried tracing the algorithm for the data from the question I get stuck quite early on because I can't tell what value for Index should be returned from FindInsertionPoint().

The input sequence is: Dublin, London, Berlin, Paris, Madrid, Copenhagen, Athens.

When all is done, the result should look like this:

I need help working out what is due to my own lack of understanding and what is due to problems with the material. It would be great to see a correct trace table for the algorithm using the data given.

In partcular, how can I work out the return values for the FindInsertionPoint() function?