enter image description here

Using the diagram of a binary tree and algorithm answer the following:

If the following commands store(1,laurence), store(1, ron), store(1,graham), store(1,abe) and store(1,martin) are executed what will be stored at location (3)?

  1. ron
  2. abe
  3. graham
  4. empty

The answer is ron but I am struggling to work out why. How does the algorithm correspond to the tree? Thanks.

  • 1
    $\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text, mathematics, and algorithms (note that you can use LaTeX) and don't forget to give proper attribution to your sources! $\endgroup$ – D.W. Apr 20 '17 at 18:08
  • 1
    $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Apr 20 '17 at 18:25

We start in store(1,laurence) and since 1 is empty, we simply put laurence in 1.

We then go in store(1,ron) and see that 1 is not empty so we compare ron to the value of 1: laurence, and since laurence$\not>$ron, we then go to store(1.upper,ron). So since 1.upper$=$3, we are now in store(3,ron). Since 3 is empty, we simply put ron in 3.

Now, since we always check that the spot is empty before settings its data, the data of 3 will never change. So at the end, it's still ron.

The tree is just here to tell you that 1.upper$=$3.

But you can "run" the algorithm on this visual representation of the tree: Start at the leftmost node. If there's nothing written, write whatever you want to write, otherwise, depending on how what you want to write compares to what is written, either go up or down.

By the way, having "upper" pointing down and "lower" poiting up is really confusing...


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.