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

Question

I'm trying to solve a similar problem (find the shortest list in a tree of lists) and I think that solving this problem would be a good start.

Given a data type like

data (Ord a, Eq a) => Tree a = Nil | Node (Tree a) a (Tree a) 

How to find the node that holds the minimum element in the binary tree above? Please not that this is not a binary search tree.

I'm trying to think recursively: The minimum is the minimum between the left, right subtrees and the current value. However, I'm struggling to translate this to Haskell code. One of the problems that I am facing is that I want to return the tree and not just the value.

Answer 1

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