Binary Search Tree
Using the applet below, you can explore binary search trees
represented as nested boxes, as described in Chapter 8 of
Concrete Abstractions. Each tree is shown as a box,
which can be either closed or open. If the box is closed, it is
shaded a dark color and you can't see what is inside of it. However,
if you click on it it will open up. Once the box is open, either you
can see that it is empty, or you can see the root value and two more
boxes for the left and right subtrees. (You can also close an open
box back up, by clicking on it again.)
Your goal is to find a specific value in the binary search tree, or to
discover that it isn't in the tree at all. You can do this by opening
the tree up, and then if necessary opening one of its subtrees, etc.
You are free to open (or close) any trees you want, even ones that
can't possibly contain the goal value, but any time you open a box,
you will be given some feedback about whether it was relevant to
finding the goal value.
For more information, see the parent web page, or contact Max Hailperin:
Email: max@gustavus.edu
Mathematics and Computer Science Department
Gustavus Adolphus College
800 W. College Avenue
St. Peter, MN 56082
USA