Clever Geek Handbook

How do I find the node that contains the minimum element in a binary tree in Haskell?

I am 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 the data type, for example

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

How do I find the node that contains 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 am struggling to translate this into Haskell code. One of the problems I am having is that I want to return a tree, not just a value.

+3


source to share


3 answers


Note. Class constraints in datatype declarations are no longer supported in Haskell 2010 and are generally deprecated. So do it 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) = ???

Please note: there is no need for limitation Eq

. Since it Eq

is a superclass Ord

, limitation Ord

implies limitation Eq

. I don't think you can even use it ==

for this.

+1


source


Here's a hint:

You can start by defining as a helper function the minimum between two trees. Node

are compared by value, ignoring subtrees, and comparison Nil

with any tree t

makes it t

minimal (in a sense, we consider it the Nil

"largest" tree). Coding this can be done in 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 minimal subtree is followed by recursion using binaryMin

:

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


source


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

  • Can a tree with min be Nil

  • A tree with min probably has a min value in the root directory

So instead of just comparing values, you may need to match patterns to subtrees to get the value of the root node.

You have not specified what the type of the function is. So let it look like this:

findmin :: Tree a -> Tree a

Now suppose you already have a function that finds the 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

You may need answers to the first two questions.

It's so hard to give an answer without giving back the actual code since your thinking is already correct.

0


source






More articles:


All Articles