Functional Programming Binary Search Tree Homework

Question

So I am having to write an insert function for a binary tree to make it a binary search tree, but I'm having some trouble. Everything is functions, so I understand that there is no concept of a state. Therefore, I need to recursively create the tree over and over when inserting. I'm having trouble wrapping my head around this idea.

treenode -> procedure(val, left, right) procedure(some) if some then -(some, 1) then right else left else val

This allows me to create nodes and access the value, the left sub-tree and right sub-tree like so (0 stands for an empty tree):

.treenode(4, 0, 0)

to create a more complex tree, I can do:

.treenode(4, .treenode(3, 0, 0), .treenode(6, .treenode(2, 0, 0), 0))

I have gotten as far as inserting into an empty tree:

insert -> procedure(root, value) if empty(root) then .treenode(value, 0, 0) else insert_recursive(root, .treenode(value, 0, 0)

This is where I cannot figure out how to insert into a tree like this. There is not concept of a state in this language so I need to somehow recursively append the new node with the value onto the current tree. If someone could give me a hint,, I would really appreciate it. The way I'm supposed to call this is:

tree = empty
tree = insert(tree, 4)
tree = insert(tree, 6)
....
and so on

Answer 1

I've never seen this grammar before, so bear with me if I got some of the syntax wrong. Hopefully the code demonstrates what needs to be done -

1. if the tree is empty, there is no value to compare against, create a singleton node with the value. This is the part you already finished.
2. otherwise, the tree is not empty, therefore we have a value to compare against. If the value to insert is less than the root's value, create a new node consisting of the root's value, insert the value into the root's left branch, and leave the root's right branch untouched
3. if the value is greater than the root's value, do the same as above, but insert the new value in the root's right branch, instead of the left
4. the value is neither less-than nor greater-than the root's value, therefore it is equal to the root's value and there is nothing left to insert. In this case, return the unmodified root

The bullet points correspond to the numbered comments below -

insert -> procedure(root, value)
  if empty(root) then           #1
    .treenode(value, 0, 0)
  else if value < root.value    #2 
    .treenode (root.value, insert(root.left, value), root.right)
  else if value > root.value    #3
    .treenode (root.value, root.left, insert(root.right, value))
  else                          #4
    root

StackOverflow allows us to run JavaScript snippets directly in answer posts. Here's a functioning snippet that allows you to see this concept in action -

const empty =
  {}

const treenode = (value, left = empty, right = empty) =>
  ({ value, left, right })

const insert = (t, value) =>
  t === empty
    ? treenode (value, empty, empty)
: value < t.value
    ? treenode (t.value, insert (t.left, value), t.right)
: value > t.value
    ? treenode (t.value, t.left, insert (t.right, value))
: t

const print = (t, pre = '', child = '') =>
  t === empty
    ? pre + '∅\n'
    : print
        ( t.right
        , child + '┌── '
        , child + '.   '
        )
    + pre + String (t.value) + '\n'
    + print
       ( t.left
       , child + '└── '
       , child + '.   '
       )

let tree = empty
tree = insert (tree, 4)
tree = insert (tree, 6)
tree = insert (tree, 9)
tree = insert (tree, 3)
tree = insert (tree, 5)
tree = insert (tree, 1)

console.log (print (tree))

The program prints the constructed tree. The ∅ symbol represents empty -

.   .   .   ┌── ∅
.   .   ┌── 11
.   .   .   └── ∅
.   ┌── 9
.   .   └── ∅
┌── 6
.   .   ┌── ∅
.   └── 5
.   .   └── ∅
4
.   ┌── ∅
└── 3
.   .   ┌── ∅
.   └── 1
.   .   └── ∅