The simplest form of tree is a

**binary tree**. A binary tree consists of- a
*node*(called the**root**node) and - left and right sub-trees.

Both the sub-trees are themselves binary trees.

You now have a

*recursively defined data structure*. (It is also possible to define a list recursively: can you see how?)A binary tree

The nodes at the lowest levels of the tree (the ones with no sub-trees) are called

**leaves**.In an

*ordered binary tree*,- the keys of all the nodes in the left sub-tree are less than that of the root,
- the keys of all the nodes in the right sub-tree are greater than that of the root,
- the left and right sub-trees are themselves ordered binary trees.

### Data Structure

The data structure for the tree implementation simply adds left and right pointers in place of the next pointer of the linked list implementation. [Load the tree struct.]

The AddToCollection method is, naturally, recursive. [Load the AddToCollection method.]

Similarly, the FindInCollection method is recursive. [Load the FindInCollection method.]

### Analysis

#### Complete Trees

Before we look at more general cases, let's make the optimistic assumption that we've managed to fill our tree neatly,

*ie*that each leaf is the same 'distance' from the root.This forms a complete tree, whose height is defined as the number of links from the root to the deepest leaf. |

First, we need to work out how many nodes,

*, we have in such a tree of height,***n***.***h**Now,

= 1 + 2n^{1}+ 2^{2}+ .... + 2^{h}

From which we have,

= 2n^{h+1}- 1

and

=hfloor( log_{2}n)

Examination of the Find method shows that in the worst case,

*+1 or***h****ceiling( log**comparisons are needed to find an item. This is the same as for binary search._{2}*n*)However, Add also requires

**ceiling( log**comparisons to determine where to add an item. Actually adding the item takes a constant number of operations, so we say that a binary tree requires_{2}*n*)**O(log***n*)*both*adding and finding an item - a considerable improvement over binary search for a*dynamic*structure which often requires addition of new items. operations forDeletion is also an

**O(log**operation.*n*)#### General binary trees

However, in general addition of items to an ordered tree will not produce a complete tree. The worst case occurs if we add an ordered list of items to a tree. What will happen? Think before you click here!

This problem is readily overcome: we use a structure known as a heap. However, before looking at heaps, we should formalise our ideas about the complexity of algorithms by defining carefully what

**O(f(**means.*n*))struct t_node {

void *item;

struct t_node *left;

struct t_node *right;

};

typedef struct t_node *Node;

struct t_collection {

int size; /* Needed by FindInCollection */

Node root;

};

static void AddToTree( Node *t, Node new ) {

Node base;

base = *t;

/* If it's a null tree, just add it here */

if ( base == NULL ) {

*t = new;

return;

}

else {

if ( KeyLess( ItemKey( new->item ), ItemKey( base->item ) ) )

{

AddToTree( &(base->left), new );

}

else

AddToTree( &(base->right), new );

}

}

void AddToCollection( Collection c, void *item ) {

Node new, node_p;

assert( c != NULL );

assert( item != NULL );

/* Allocate space for a node for the new item */

new = (Node)malloc(sizeof(struct t_node));

/* Attach the item to the node */

new->item = item;

new->left = new->right = (Node)0;

AddToTree( &(c->node), new );

}

/* Binary tree implementation of a collection */

/* Now we need to know whether one key is less, equal or greater than

another

*/

extern int KeyCmp( void *a, void *b );

/* Returns -1, 0, 1 for a < b, a == b, a > b */

void *FindInTree( Node t, void *key ) {

if ( t == (Node)0 ) return NULL;

switch( KeyCmp( key, ItemKey(t->item) ) ) {

case -1 : return FindInTree( t->left, key );

case 0: return t->item;

case +1 : return FindInTree( t->right, key );

}

}

void *FindInCollection( collection c, void *key ) {

/* Find an item in a collection

Pre-condition: (c is a collection created by a call to ConsCollection) &&

(key != NULL)

Post-condition: returns an item identified by key if

one exists, otherwise returns NULL

*/

assert( c != NULL );

assert( key != NULL );

/* Select node at head of list */

return FindInTree( c->root, key );

}

## Key terms |

**Root Node**- Node at the "top" of a tree - the one from which all operations on the tree commence. The root node may not exist (a NULL tree with no nodes in it) or have 0, 1 or 2 children in a binary tree.
**Leaf Node**- Node at the "bottom" of a tree - farthest from the root. Leaf nodes have no children.
**Complete Tree**- Tree in which each leaf is at the same distance from the root. A more precise and formal definition of a complete tree is set out later.
**Height**- Number of nodes which must be traversed from the root to reach a leaf of a tree.