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:
Mathematics and Computer Science Department
Gustavus Adolphus College
800 W. College Avenue
St. Peter, MN 56082