CSE 143/AC : 15 August 2000

Trees and tree operations

Definitions of a binary tree

There are many roughly equivalent definitions of a binary tree. Here are two:

1. A binary tree is an acyclic, fully connected, directed graph with a maximum outdegree of 2 at each node and a distinguished vertex called the root, such that every other node is reachable from the root.

2. A binary tree is either the nil tree, or a node containing a key value and two children which are also trees.

In practice, the second is much more useful (in fact, don't think too hard about the first one). We typically define a BinaryTree node as follows:

struct TreeNode { int key; TreeNode *left, *right; TreeNode(int key, TreeNode *left = NULL, TreeNode *right = NULL) : key(key), left(left), right(right) {} };

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 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.