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:

enter image description here

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

Index ← RootPointer


// if no free node report an error
    IF FreePointer = -1
            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 

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:

enter image description here

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?

Thanks in advance.

Below is an image of the algorithm given in the solutions (same as pseudocode above).

enter image description here

  • $\begingroup$ You say "the description in the question". What question? Please reference the source of all copied material (including code or images/screenshots). $\endgroup$ – D.W. Apr 7 '19 at 15:44
  • $\begingroup$ Cambridge International Examinations A Level past paper 2017. $\endgroup$ – Robin Andrews Apr 7 '19 at 15:54
  • $\begingroup$ Please edit the question to put it in your post, not in the comments. The comments exist to help you improve your question. Thank you! $\endgroup$ – D.W. Apr 7 '19 at 17:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.