1 files changed, 14 insertions, 6 deletions
diff --git a/tree.sml b/tree.sml
index 597e469..57e9a24 100644
--- a/tree.sml
+++ b/tree.sml
@@ -1,16 +1,24 @@
 structure Tree: TREE = struct
   datatype ('k, 'v) t = Node of 'k * 'v * ('k, 'v) t * ('k, 'v) t | Empty
 
-  exception Exists
-
   val empty = Empty
 
-  fun insert _ Empty k v = Node (k, v, Empty, Empty)
+  fun insert _ Empty k v = (NONE, Node (k, v, Empty, Empty))
     | insert cmp (Node (k', v', left, right)) k v =
         case cmp k k' of
-          LESS => Node (k', v', insert cmp left k v, right)
-        | EQUAL => raise Exists
-        | GREATER => Node (k', v', left, insert cmp right k v)
+          LESS =>
+          let
+            val (res, left) = insert cmp left k v
+          in
+            (res, Node (k', v', left, right))
+          end
+        | EQUAL => (SOME v', Node (k, v, left, right))
+        | GREATER =>
+          let
+            val (res, right) = insert cmp right k v
+          in
+            (res, Node (k', v', left, right))
+          end
 
   fun lookup _ Empty _ = NONE
     | lookup cmp (Node (k', v', left, right)) k =