============================================================================
           Faculty of Applied Science and Engineering, University of Toronto
                     CSC181: Introduction to Computer Programming, Fall 2000

Supplemental Notes: Binary Search Trees
============================================================================

Note: Refer to the lecture slides for an introduction to trees.

------------
Introduction
------------

A binary search tree (BST) is a binary tree wherein each node has a
'key' (a number, a string, or some other item that can be compared
using relational operators/functions).

Furthermore, for each node x in the BST, x's key is

  - greater than the keys of all of the nodes in x's left subtree

  - less than the keys of all of the nodes in x's right subtree

(This is known as the "binary search tree property".)

Note that this means that every subtree in a BST is itself a BST. This
comes in handy when designing algorithms that work on a BST.

-----------------------
A Linked Implementation
-----------------------

We can use a linked data structure to implement a BST:

struct bstnode {
    int key;
    struct bstnode* left;
    struct bstnode* right;
};

Each node contains its key, as well as pointers to its left and right
children. If the left pointer is NULL, then this node has no left
child (and the same interpretation can be made for the right pointer).

We will also need a pointer to the root of the tree, which we can
encapsulate within another structure:

struct bst {
    struct bstnode* root;
};

If the root pointer is NULL, then the tree is empty.

----------------
Search/Retrieval
----------------

Searching for elements in a BST is much like performing a binary
search on a sorted array.

What we want: Given a key k, determine whether or not the BST rooted
at node r contains k.

Basic idea:

              r
             /
            c
           / \
          ?   ?

c is root of subtree possibly containing k, and c->key could be == k

c's left subtree contains elements < c->key, c's right subtree
contains elements > c->key, and k could be in either of these subtrees

Initialization: c = r

Exit condition: c == NULL (unsuccessful) or k == c->key (successful)

Body: Examine key(c), if k > c->key, search right subtree; if k <
c->key, search left subtree.

---------
Insertion
---------

Inserting an element into a BST is much like performing insertion into
a sorted array.

What we want: Given a key k, insert it into the BST rooted at node r

Basic idea:

- Determine where we end up if the search is unsuccessful. For a
  linked BST, this will be a NULL root pointer if the tree is empty,
  or some NULL child pointer, otherwise.

- Insert new node with key k at this point.

Example:

Here is what a BST looks like after a sequence of insertions <6, 2,
1, 8, 4, 9>:

-----------
6
-----------
  6
 /
2
-----------
    6
   /
  2
 /
1
-----------
    6
   / \
  2   8
 /
1
-----------
    -6-
   /   \
  2     8
 / \
1   4
-----------
    -6-
   /   \
  2     8
 / \     \
1   4     9
-----------

----------
References
----------

1. D. Horton and P. Gries, CSC148 Lecture Notes, Fall 1999.