How to find the node that holds the minimum element in a binary tree in Haskell?

Here's a hint:

You can start by defining, as an auxiliary function, a minimum between only two trees. Nodes are compared according to ther value, ignoring the subtrees, and comparing Nil to any tree t makes t the minimum (in a sense, we think of Nil as the "largest" tree). Coding this can be done by cases:

binaryMin :: Ord a => Tree a -> Tree a -> Tree a
binaryMin Nil t = t
binaryMin t Nil = t
binaryMin (Node l1 v1 r1) (Node l2 v2 r2) = ???

Then, the minimum subtree follows by recursion, exploiting binaryMin:

treeMin :: Ord a => Tree a -> Tree a
treeMin Nil = Nil
treeMin (Node left value right) = ???
   where l = treeMin left
         r = treeMin right

Note: class constraints on datatype declarations are no longer supported in Haskell 2010, and generally not recommended. So do this instead:

data Tree a =   Nil
              | Node (Tree a) a (Tree a)

Think recursively:

getMinTree  :: Ord a => Tree a -> Maybe (Tree a)
getMinTree = snd <=< getMinTree'

getMinTree' :: Ord a => Tree a -> Maybe (a, Tree a)
getMinTree' Nil = ???
getMinTree' (Node Nil value Nil) = ???
getMinTree' (Node Nil value right) = ???
getMinTree' (Node left value Nil) = ???
getMin' (Node left value right) = ???

Note also: there is no need for an Eq constraint. Since Eq is a superclass of Ord, an Ord constraint implies an Eq constraint. I don't think you're even likely to use == for this.

You have the correct understanding. I think you should be fine when you can prove the following:

• Can the tree with min be Nil
• The tree with min probably has the min value at the root

So instead of just comparing the values, you might need to pattern-match the subtrees to get the value of the root node.

You didn't mention what the type of the function is. So, let's suppose it looks like so:

findmin :: Tree a -> Tree a

Now, suppose you already have a function that finds min of the tree. Something like:

findmin Nil = Nil -- no tree - no min
findmin (Node l x r) = case (findmin ..., findmin ...) of
       -- like you said, find min of the left, and find min of the right
       -- there will be a few cases of what the min is like on the left and right
       -- so you can compare them to x
                         some case -> how to find the min in this case
                         some other case -> how to find min in that other case

Perhaps, you will need to know the answers to the first two questions.

It is so hard to give an answer short of giving away the actual code, since your thinking is already correct.