====================================================================
Binary Search Tree
====================================================================

BinarySearchTree(R) is the domain of binary trees with elements of
type R, ordered across the nodes of the tree.  A non-empty binary
search tree has a value of type R, and right and left binary search
subtrees.  If a subtree is empty, it is displayed as a period ``.``.

Define a list of values to be placed across the tree.  The resulting
tree has 8 at the root; all other elements are in the left subtree. ::

  lv := [8,3,5,4,6,2,1,5,7]
   [8, 3, 5, 4, 6, 2, 1, 5, 7]
                      Type: List PositiveInteger

A convenient way to create a binary search tree is to apply the
operation binarySearchTree to a list of elements. ::

  t := binarySearchTree lv
   [[[1, 2, .], 3, [4, 5, [5, 6, 7]]], 8, .]
                      Type: BinarySearchTree PositiveInteger

Another approach is to first create an empty binary search tree of integers. ::

  emptybst := empty()$BSTREE(INT)
   [] 
                      Type: BinarySearchTree Integer

Insert the value 8.  This establishes 8 as the root of the binary
search tree.  Values inserted later that are less than 8 get stored in
the left subtree, others in the right subtree. ::

  t1 := insert!(8,emptybst)
   8 
                      Type: BinarySearchTree Integer

Insert the value 3. This number becomes the root of the left subtree
of t1.  For optimal retrieval, it is thus important to insert the
middle elements first. ::

  insert!(3,t1)
   [3, 8, .]
                      Type: BinarySearchTree Integer

We go back to the original tree t.  The leaves of the binary search
tree are those which have empty left and right subtrees. ::

  leaves t
   [1, 4, 5, 7]
                      Type: List PositiveInteger

The operation split(k,t) returns a record containing the two subtrees:
one with all elements "less" than k, another with elements "greater"
than k. ::

  split(3,t)
   [less=[1, 2, .], greater=[[., 3, [4, 5, [5, 6, 7]]], 8, .]]
              Type: Record(less: BinarySearchTree PositiveInteger,greater: 
                           BinarySearchTree PositiveInteger)

Define insertRoot to insert new elements by creating a new node. ::

  insertRoot: (INT,BSTREE INT) -> BSTREE INT
                      Type: Void

The new node puts the inserted value between its "less" tree and
"greater" tree. ::


  insertRoot(x, t) ==
    a := split(x, t)
    node(a.less, x, a.greater)
                      Type: Void


Function buildFromRoot builds a binary search tree from a list
of elements ls and the empty tree emptybst. ::

  buildFromRoot ls == reduce(insertRoot,ls,emptybst)
                      Type: Void

Apply this to the reverse of the list lv. ::

  rt := buildFromRoot reverse lv
   [[[1, 2, . ], 3, [4, 5, [5, 6, 7]]], 8, .]
                      Type: BinarySearchTree Integer

Have FriCAS check that these are equal. ::

  (t = rt)@Boolean
   true
                      Type: Boolean

See Also:

* ``)show BinarySearchTree``