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);         // Constructor
    ~binTree(void);        // Destructor

    void add(int item);    // Add function
    void remove(int item); // Remove function
    bool search(int item); // Search function
    void print(void);      // Print function
  
  private:
    binTreeNode *root;     // Root pointer

    // ...
    // The extra functions needed for implementation are put here
};

class binTreeNode {
  public:
    int data;                 // Actual data
    binTreeNode *left_child;  // Left child pointer
    binTreeNode *right_child; // Right child pointer
};

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);  // Left child first
  cout << node->data << endl;   // Then this node
  printTree(node->right_child); // Then 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.)