Finding floor & ceiling in BST with Haskell

Question

I've been given the following piece of code and I'm expected to complete it. The purpose is to design a function which will calculate the floor of a given element k in a BST. The floor of an element 'k' in a BST is the greatest key that is smaller than 'k'.

I'm really at a loss... I've already programmed this for Java, but haven't been able to work it out in Haskell.

floor :: Ord a => a -> ABST a -> Maybe a
floor x Empty    = Nothing
floor x (Node y w lt rt) 
  | x == y       = Just y
  | x < y = undefined
  | x > y = undefined

Thank you in advance.

Answer 1

You could try to check whether the "natural" recursive calls help in solving this problem.

That is, consider:

floor :: Ord a => a -> ABST a -> Maybe a
floor x Empty    = Nothing
floor x (Node y w lt rt) 
  | x == y       = Just y
  | x < y = ???
  | x > y = ???
  where floorL = floor x lt
        floorR = floor x rt

Then, is there some way to exploit floorL,floorR to achieve the wanted result?