## Issue

I am new to SML and am trying to implement a BST. I have figured out how to parse through the tree, but am struggling with creating an insert function. I want the function to be: insert(bst, key, value) of type BST * int * int -> BST where it inserts a key-value pair into a given tree and returns the resulting tree. I am struggling in the creation of this though, because I get a bit confused on making sure the function is of the right type.

Here is my code so far, I have included an example tree as well

```
(* left subtree, right subtree, key, value *)
datatype BST = Empty | Node of BST * BST * int * int;
fun parsePost [] = Empty
| parsePost lst =
let
fun pP(stack, (0, k, v)::str) = pP(Node(Empty, Empty, k, v)::stack, str)
| pP(L::stack, (1, k, v)::str) = pP(Node(L, Empty, k, v)::stack, str)
| pP(R::stack, (2, k, v)::str) = pP(Node(Empty, R, k, v)::stack, str)
| pP(R::L::stack, (3, k, v)::str) = pP(Node(L, R, k, v)::stack, str)
| pP(T::stack, []) = T;
in
pP([], lst)
end;
val exTree1 = [(0, 1, 1), (0, 3, 3), (3, 2, 2)];
```

I was thinking of starting off the insert function as so:

```
fun insert(Empty, x, y) = Empty
```

But I am not quite sure where to go from there.

## Solution

If you insert a key and value pair into an empty tree, do you really expect to get an empty tree back? I very much doubt this is what you’d expect.

Rather you’d probably expect a tree with that pair, but with empty branches.

```
fun insert(Empty, x, y) = Node(Empty, Empty, x, y)
```

What if the tree is *not* empty, though?

Let’s consider a simple example:

```
val ex1 = Node(Empty, Empty, 1, 4)
```

This looks like:

```
(1,4)
/ \
/ \
/ \
Empty Empty
```

Well, if we evaluate `insert(ex1, 2, 5)`

then presumably the result should look like:

```
(1,4)
/ \
/ \
/ \
Empty (2,5)
/ \
/ \
/ \
Empty Empty
```

To get this we have to realize that the right branch is the same result we’d get if we evaluated `insert(Empty, 2, 5)`

.

```
(2,5)
/ \
/ \
/ \
Empty Empty
```

So as the tree data type is recursive, so is your solution. We need to check if the key you want to insert is the same as the key already stored in a node. If it is, we don’t have to change anything.

If it’s less than the key already present, we insert into the left branch, and if it’s greater than, we insert into the right branch.

```
fun insert(Empty, x, y) = Node(Empty, Empty, x, y)
| insert((n as Node(l, r, k, v)), x, y) =
case Int.compare(x, k) of
EQUAL => n
| LESS => Node(insert(l, x, y), r, k, v)
| GREATER => Node(l, insert(r, x, y), k, v)
```

This strategy scales to any depth of tree structure, because eventually a branch will always either contain the key you’re looking for, or have an empty branch.

Answered By – Chris

Answer Checked By – Mary Flores (BugsFixing Volunteer)