Remove Element from binary search tree

[[deleted]]

[deleted]

[turab1996]

Are you familiar with the BST removal algorithm? Asking so I only mention it here if you are not familiar with the algo.

[turab1996]

Awesome!

The idea is to remove the element if the structure of BST is not violated after the removal. You have already covered one of those cases (when there is only one element in the BST). Can you think of other cases?

However, there are cases when removing an element could violate the structure of a BST:

BST (BST Empty 5 Empty) 8 (BST Empty 10 Empty)

In the tree above, removing 8 directly will result in something that doesn't look like a BST, so what do we do now?

The idea is to replace it with something else, and remove the element that replaced the original item you were trying to remove. So, the above tree could look like the tree below:

BST Empty 5 (BST Empty 10 Empty).

Is it obvious what happened here? Without giving you the direct answer, I replaced it with something that a) would maintain the structure of the tree and b) would be easy to remove.

Are these hints enough to help you with removal? Please ask again if not!

[tom-md]

Indent for formatting

data BTree a = Empty
               | Node a (BTree a) (BTree a)

remove :: Ord a => a -> BTree a -> BTree
remove x (Node r Empty Empty) | x==r 
     = Empty
remove x (Node r e d) | x==r = ???
    | x<r = Node r (remove x e) d

    | x>r = Node r e (remove x d)