Well if you haven't taken your exam yet, here is some info. If you need any more detail about anything, just ask what specifically you need.

A binary tree is either an empty set of nodes or a set of nodes with one node designated as the root. Each node has two subtrees, the left subtree and right subtree descending from it.

The binary search tree is an ordered binary tree in which each node contains an item, in which all items in the left subtree precede the root item, and the root item precedes all the items in the right subtree.

For example:
----------------|melon|----------------
----------------/-----\----------------
---------|apple|-------|orange|--------
---------/-----\-------/------\--------
----|NULL|--|lemon|--|NULL|--|pear|----

Lemon is less than melon, but greater than apple. And pear is greater than lemon and greater than orange.

To make the tree you would need functions to:
-Initialize the tree to empty
-Determine whether the tree is empty
-Determine whether the tree is full
-Determine the number of items in the tree
-Add an item to the tree
-Delete an item from the tree
-Search the tree for an item
-Visit each item of in the tree

Well that's about it. Need anything else just ask.

Could anyone give a clear explanation of a dynamic programming algorithm for building an optimal binary search tree? I've spent the last two hours poring over the measly two pages that my Algorithm Analysis book gives the topic, and another hour searching the net, and I still haven't been able to pin the thing down =( Of course, I'm required to understand the algorithm for an exam =/

Thanks,
--Feyr

Feyr,
Are you referring to a balanced tree? If you can hold out until Thursday night, I have a couple books at home that I can look through for you.

Six