SML Binary Search Tree Insert Function

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.

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.