trie_tree_insert.ml

let rec insert: 'a. key -> 'a -> 'a trie -> 'a trie =
  fun tree value trie -> match (tree, trie) with
    | (Empty, Trie (_, children)) -> Trie (Some value, children)
    | (Node (root, left, right), Trie (trieValue, children)) ->
      let trieForRoot = try
        M.find root children
      with
        Not_found -> empty
      in
      let trieForLeft = try
        find left trieForRoot
      with
        Not_found -> empty
      in
      let newTrieForLeft = insert right value trieForLeft in
      let newTrieForRoot = insert left newTrieForLeft trieForRoot in
      let newChildren = M.add root newTrieForRoot children in
      Trie (trieValue, newChildren)