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