CODEWITHSUNDEEP
haskelltree
user35477
user35477

Reputation: 151

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

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.

Upvotes: 3

Views: 2193

Answers (3)

dfeuer
dfeuer

Reputation: 48591

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.

Upvotes: 1

chi
chi

Reputation: 116139

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

Upvotes: 1

Sassa NF
Sassa NF

Reputation: 5406

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.

Upvotes: 0

Related Questions