Go to the Next or Previous section, the Detailed Contents, or the Amiga E Encyclopedia.

## 16.3 Binary Trees

This is an example of a recursive type and the effect it has on functions which manipulate this type of data. A binary tree is like a linked list, but instead of each element containing only one link to another element there are two links in each element of a binary tree (which point to smaller trees called branches). The first link points to the left branch and the second points to the right branch. Each element of the tree is called a node and there are two kinds of special node: the start point, called the root of the tree (like the head of a list), and the nodes which do not have left or right branches (i.e., `NIL` pointers for both links), called leaves. Every node of the tree contains some kind of data (just as the linked lists contained an E-string or E-list in each element). The following diagram illustrates a small tree.

```            +------+
| Root |
+--*---+
/ \
Left /   \ Right
/     \
+------*       *------+
| Node |       | Node |
+--*---+       +--*---+
/              / \
Left /         Left /   \ Right
/              /     \
+--*---+     +----*-+   +-*----+
| Leaf |     | Leaf |   | Leaf |
+------+     +------+   +------+
```

Notice that a node might have only one branch (it doesn't have to have both the left and the right). Also, the leaves on the example were all at the same level, but this doesn't have to be the case. Any of the leaves could easily have been a node which had a lot of nodes branching off it.

So, how can a tree structure like this be written as an E object? Well, the general outline is this:

```OBJECT tree
data
left:PTR TO tree, right:PTR TO tree
ENDOBJECT
```

The `left` and `right` elements are pointers to the left and right branches (which will be `tree` objects, too). The `data` element is some data for each node. This could equally well be a pointer, an `ARRAY` or a number of different data elements.

So, what use can be made of such a tree? Well, a common use is for holding a sorted collection of data that needs to be able to have elements added quickly. As an example, the data at each node could be an integer, so a tree of this kind could hold a sorted set of integers. To make the tree sorted, constraints must be placed on the left and right branches of a node. The left branch should contain only nodes with data that is less than the parent node's data, and, similarly, the right branch should contain only nodes with data that is greater. Nodes with the same data could be included in one of the branches, but for our example we'll disallow them. We are now ready to write some functions to manipulate our tree.

The first function is one which starts off a new set of integers (i.e., begins a new tree). This should take an integer as a parameter and return a pointer to the root node of new tree (with the integer as that node's data).

```PROC new_set(int)
DEF root:PTR TO tree
NEW root
root.data:=int
ENDPROC root
```

The memory for the new tree element must be allocated dynamically, so this is a good example of a use of `NEW`. Since `NEW` clears the memory it allocates all elements of the new object will be zero. In particular, the `left` and `right` pointers will be `NIL`, so the root node will also be a leaf. If the `NEW` fails a `"MEM"` exception is raised; otherwise the data is set to the supplied value and a pointer to the root node is returned.

To add a new integer to such a set we need to find the appropriate position to insert it and set the left and right branches correctly. This is because if the integer is new to the set it will be added as a new leaf, and so one of the existing nodes will change its left or right branch.

```PROC add(i, set:PTR TO tree)
IF set=NIL
RETURN new_set(i)
ELSE
IF i<set.data
ELSEIF i>set.data
ENDIF
RETURN set
ENDIF
ENDPROC
```

This function returns a pointer to the set to which it added the integer. If this set was initially empty a new set is created; otherwise the original pointer is returned. The appropriate branches are corrected as the search progresses. Only the last assignment to the left or right branch is significant (all others do not change the value of the pointer), since it is this assignment that adds the new leaf. Here's an iterative version of this function:

```PROC add_iter(i, set:PTR TO tree)
DEF node:PTR TO tree
IF set=NIL
RETURN new_set(i)
ELSE
node:=set
LOOP
IF i<node.data
IF node.left=NIL
node.left:=new_set(i)
RETURN set
ELSE
node:=node.left
ENDIF
ELSEIF i>node.data
IF node.right=NIL
node.right:=new_set(i)
RETURN set
ELSE
node:=node.right
ENDIF
ELSE
RETURN set
ENDIF
ENDLOOP
ENDIF
ENDPROC
```

As you can see, it's quite a bit messier. Recursive functions work well with manipulation of recursive types.

Another really neat example is printing the contents of the set. It's deceptively simple:

```PROC show(set:PTR TO tree)
IF set<>NIL
show(set.left)
WriteF('\d ', set.data)
show(set.right)
ENDIF
ENDPROC
```

The integers in the nodes will get printed in order (providing they were added using the `add` function). The left-hand nodes contain the smallest elements so the data they contain is printed first, followed by the data at the current node, and then that in the right-hand nodes. Try writing an iterative version of this function if you fancy a really tough problem.

Putting everything together, here's a `main` procedure which can be used to test the above functions:

```PROC main() HANDLE
DEF s, i, j
Rnd(-999999)    /* Initialise seed */
s:=new_set(10)  /* Initialise set s to contain the number 10 */
WriteF('Input:\n')
FOR i:=1 TO 50  /* Generate 50 random numbers and add them to set s */
j:=Rnd(100)