CSE 143/AE : 15 August 2000

Trees and tree operations

Definitions of a binary tree

A binary tree is either

• The nil tree, or
• A node containing two parts:
  1. A key value, and
  2. two children which are also trees.

struct TreeNode { int key; TreeNode *left, *right; };

The nil tree, in this case, would be a NULL pointer (that is, a pointer to no node).

Binary search trees

A binary search tree is simply a tree which satisfies the following invariant:

For any node x,
• the keys of all items in the left subtree of x are less than or equal to x's key, and
• keys of all items in the right subtree are greater than x's key.

We can define a class for a binary search tree as follows:

class BinaryTree { public: BinaryTree() : root(NULL) {} void insert(int value); bool find(int value); bool delete(int value); bool isEmpty(); int size(); private: TreeNode *root; };

Notice that nothing in particular distinguishes this class interface from that of, say, a Vector. The chief difference is that, since this class is documented to be a binary tree, the user will expect that its operations have typical binary tree performance characteristics.