# Introduction

This is an implementation of binary trees in LSL using flattened lists as data representation and functions for operations.

LSL's single compound data-structure is the `list`

(which does not accept lists as subtype) which makes the task somewhat more difficult than typical Object Oriented-programming where we could easily (without references) create a node object holding the `left`

, `parent`

, `right`

node.

In order to work around that, nodes are represented by `strings`

and the tree is represented by a flat `list`

. We start from three simple formulas that give us the `left`

, `parent`

and `right`

of a node and on top of those three logical primitives, we build a fully-blown implementation of binary trees and binary search trees.

# Left, Parent and Right

The index of the left-node is given by:

The index of the right-node is given by:

The index of the parent of a node is given by:

## Binary Tree with Two Children

Suppose we insert the nodes "M", "L", "P" into a binary-tree, a representation thereof being:

M
/ \
L P

This translates to a flattened list as:

list BT = [ "M", "L", "P" ]

where "M" represents the root node, "L" represents the left child of "M" and "P" represents the right child of "M". The parents of both "L" and "P", is "M".

# Binary Search Trees

A binary-tree implementation is the foundation on which we build the binary search trees. In fact, we first build a minimal binary tree implementation and then use the same functions to construct operations such as `delete`

and `insert`

which make sense in the case of binary search trees.

One problem is determining the sequence of nodes, for which we create a wrapper function to Ord, called `wasOrdCompare`

which is used in the `insert`

, `delete`

and `search`

operations for the binary search tree implementation.

The `Ord`

function (not created by Wizardry and Steamworks but by Pedro Oval) and the wrapper `wasOrdCompare`

are optional but we used them because they allow the `insert`

, `delete`

and `search`

to work on some level of "generic" types ^{1)}, giving order to numbers and strings. For example, it helps to distinguish whether "dog" is "bigger" than "cat", in a lexicographical sense, so that they can be inserted into the binary search tree in relative positions.

In case the binary search tree is meant to store numbers, is feasible to replace `Ord`

and thus `wasOrdCompare`

with something like:

integer wasOrdCompare(float a, float b) {
// 1 if a is greater than b.
if(a > b) return 1;
// -1 if a is smaller than b.
if(a < b) return -1;
// 0 if they are equal.
return 0;
}

thereby eliminating a large chunk of code.

A different difficulty is that due to the lack of objects, and since we cannot create a node datatype, deletion cannot be performed by substituting the corresponding nodes with their descendants and then implicitly having the subtree "move itself". Thus, you will notice that the `delete`

function has to "manually" move the entire subtree after substituting the node to be deleted.

# Index