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.
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
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 // adjust free pointer 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
Thanks in advance.
Below is an image of the algorithm given in the solutions (same as pseudocode above).