#| 
   A Binary Tree is a tree where each node has at most 2 children.
   For orderable values (e.g. numbers with <, strings alphabetically, etc),
    a Binary *Search* Tree (BST) stores a set of (unique) values in a certain way.

   Each node contains a value.
     All values in the left subtree are less than the value.
     All values in the right subtree are more than the value.

   We discussed pre and post order traversal of trees.
   For binary trees there is also in-order traversal:
     left sub-tree, self, right sub-tree
   So a BST holds its values such that in-order traversal visits them in order.

   Both sorted arrays and relatively "wide and flat" BSTs allow fast access
    relative to the number of elements. But BSTs also allow fast insertion
    and deletion since relatively few elements need moving/adjustment.
|#

#| A structure datatype for nodes in a BST.

   As the root node of a tree, a node is also used to represent the tree of nodes
    "under" the node.

   The define-struct makes corresponding functions:
     make-bst
     bst-left bst-value bst-right
     bst?

   Since it was declared mutable, the fields can be changed after make-bst, with:
     set-bst-left! set-bst-value! set-bst-right!

   A bst will be assumed to hold its values in order.
   Also, #f will be consider an empty "bst" |#

[define-struct bst [left value right] #:mutable]

; A simple bst of numbers.
[define t0 [make-bst [make-bst #f 1 #f] 2 [make-bst #f 3 #f]]]

#| For a bst t, print out the values in t and its subtrees in order,
    one per line. |#
[define display-bst
    [lambda [t]
        [when t
            [display-bst [bst-left t]]
            [newline] [display [bst-value t]]
            [display-bst [bst-right t]]]]]

#| For a number v and bst t holding numbers, where v is not in t,
    inserts v into t and returns the updated t |#
[define insert-bst
    [lambda [v t]
        [if t
            [begin ; multiple statements, for side-effects, last value returned
                [if [< v [bst-value t]]
                    [set-bst-left! t [insert-bst v [bst-left t]]]
                    [set-bst-right! t [insert-bst v [bst-right t]]]]
                t]                
            [make-bst #f v #f]]]]

; Try it out
[display-bst t0]
[newline]
[display-bst [insert-bst 2.5 t0]]