**Binary
Search Trees**

(Up to Basic
Computer Science : Data Trees)

**Binary search trees** (also known as just **binary trees**)
are ordered trees in which all nodes have **no more than two children**.
The parent node is always **greater** than all of the data in
the left sub-tree that extends from the left child node, and the
parent node is **less** than all of the data in the right sub-tree
that extends from the right child node.

Here is the basic framwork for the binary search tree:

**class** binTree {
**public**:
binTree(**void**);
~binTree(**void**);
**void** add(**int** item);
**void** remove(**int** item);
**bool** search(**int** item);
**void** print(**void**);
**private**:
binTreeNode *root;
};
**class** binTreeNode {
**public**:
**int** data;
binTreeNode *left_child;
binTreeNode *right_child;
};

This code is very similar to the code of the linked
list, but the node here is differs from the node to the linked
list in that this binTreeNode
points to *two* other nodes instead of just one.

Since the left child is always less than the parent and the right
child is greater than the parent, the tree can easily print an ordered
list of all of the elements with the following algorithm, also known
as **in-order traversal**:

**void** printTree(binTreeNode *node) {
printTree(node->left_child);
cout << node->data << endl;
printTree(node->right_child);
}

To print the tree, you would call the function with the value of root. Each time, the function would keep
calling itself (**recursion!**) until it reaches the leftmost
node, which is the least value in the entire tree. Then, it would
cycle through the entire tree, and then the right children, until
it reaches the rightmost, or greatest, value in the tree.

Other traversals of trees are **pre-order** and **post-order
traversals**. In pre-order, the root is processed first, then
the left children, and then the right children. In post-order, the
left children and right children are processed before the root.

Try writing the code for the binary tree as an exercise. It's a
little tricky this time, especially with the remove()
function. (*HINT:** Most of the functions require
helper, or auxiliary, functions. Some, but definitely not all, of
the functions may be recursive.)*