## Insertion

To insert a new value "*value*" into a binary search tree *T*,
we use the procedure **TREE_INSERT**. This procedure receives the
value to insert and the tree pointer *T*. It traverses the tree
recursively until it finds the right place of insertion, and updates
the tree structure accordingly.
The pseudo-code shown below illustrates how **TREE_INSERT** works. The
procedure starts at the *root* of the tree and traces a recursive path
downward. The if statement at line 3 tests if the value to be inserted
is less than the actual value in the node pointed by *T*. If this
condition is true, the procedure calls itself recursively, but this time
it passes the left subtree of *T* as a parameter. The reason for
that follows straight from the Binary Search Tree property, which states
that smaller values should always be left-descendents of their
respective ancestors. Conversely, if *value* is greater than
the value of *T*, it passes the right subtree of *T* as a
parameter for the next recursive call in line 5. **TREE_INSERT**
terminates after it finds a *NIL* child (a new leaf is always
created as a result of this procedure) and it backtracks from its
recursive calls, updating the tree structure.

### Pseudo-Code

TREE_INSERT (T, value)
begin
1. if (T = NIL) then
2. T = alloc_node(NIL);
3. else if (val < T->value) then
4. TREE_INSERT (T->left, val);
5. else TREE_INSERT(T->right, val);
6. end.

### Example

The following images were created for the application using
Macromedia Director 4.0.

Previous Page

Next Page

Return to Main Page