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.

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:

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

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 ¹⁾, 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.