delete node from binary search tree, haskell

Question

I'm making a Haskell function to delete a node from a Binary Search Tree. I know the rules regarding the action needed to be taken depending on the number children the targeted parent has.

no children - delete, 1 child - replace with the child, 2 children - find the min in the right sub tree and replace the node with the value, - then, recursively delete the minimum value from the right sub-tree

data BST = MakeNode BST String BST
              |  Empty

deleteNode :: String -> BST



treeBuilder :: [String] -> BST
treeBuilder = foldr add Empty

add :: String -> BST -> BST
add new Empty = (MakeNode Empty new Empty)
add string tree@(MakeNode left value right)
    | string > value = MakeNode left value (add string right)
    | string < value = MakeNode (add string left) value right
    | otherwise = tree

can't figure out why treeBuilder isn't working correctly either. It just prints Strings Diagonally down to the right.

Answer 1

In these situations, it's best not to think about deleting a node from the tree; it's better to think of how to transform the tree you have into one without the node you want gone.

Let's do some case analysis:

If the tree is empty, then the result is empty, regardless of the key:

delete _ Empty = Empty

If the tree is non-empty, we have to see if the key matches the node. If it does not match, then we need to transform either the left or right subtree based upon whether the key is greater-than or less-than the node:

delete key (MakeNode l key' r) | key < key' = MakeNode (delete key l) key' r
delete key (MakeNode l key' r) | key > key' = MakeNode l key' (delete key r)

If it does match (which it must, since all of the no-match cases have been dealt with), then we have to figure out how to create a new tree without the root node. From your description, if the node has no children, just delete it:

delete _ (MakeNode Empty _ Empty) = Empty

If the node has one child, use that:

delete _ (MakeNode l _ Empty) = l
delete _ (MakeNode Empty _ r) = r

Otherwise, find and delete the minimum key in the right subtree, and use it as the new root's key:

delete _ (MakeNode l _ r) = MakeNode l key r' -- make a new root with min key and new r
  where key = minKey r    -- find the minimum key in the right subtree
        r' = delete key r -- new right subtree with min key removed

        -- a helper function to find the minimum key in a tree
        -- !! does not work on Empty tree !!
        minKey (MakeNode Empty key _) = key
        minKey (MakeNode l _ _) = minKey l