CODEWITHSUNDEEP
haskell
skills
skills

Reputation: 327

Retrieve minimum from tree and the tree itself - haskell

With this function, i can remove the minimum in a binary search tree:

data BTree a = Empty
             | Node a (BTree a) (BTree a)

semmin :: BTree a -> BTree a
semmin (Node x Empty Empty) = Empty
semmin (Node x l r) = Node x (semmin l) r

I want to retrieve the minimum value and the tree without this minimum, the trick is, i can traverse it only once.

The type is mimSmim :: BTree a -> (a,BTree a)

how should i do it?

EDIT: Does this count as one traverse?

semmin :: BTree a -> (a,BTree a)
semmin (Node x Empty Empty) = (x,Empty)
semmin (Node x l r) = let i= (semmin l)
                       in (fst(i),(Node x (snd(i)) r))

Upvotes: 0

Views: 633

Answers (3)

chi
chi

Reputation: 116174

The posted code is on the right track, even if not completely correct:

semmin :: BTree a -> (a,BTree a)
semmin (Node x Empty Empty) = (x,Empty)
semmin (Node x l r) = let i= (semmin l)
                       in (fst(i),(Node x (snd(i)) r))

As a hint for improving your code, not that the following crashes:

semmin (Node 1 Empty (Node 2 Empty Empty))

Also, to improve readability a bit, I would suggest:

semmin :: BTree a -> (a,BTree a)
semmin (Node x Empty Empty) = (x,Empty)
semmin (Node x l r) = let (minValue, minTree) = semmin l
                       in (minValue, Node x minTree r)

Finally, this looks as if it's returning the whole tree back, instead of the tree at which the minimum is found. Check if that's the case, and if that's what you want.

Upvotes: 0

Andrew Monshizadeh
Andrew Monshizadeh

Reputation: 1794

You are looking for a zipper. A [zipper][1] is a representation of another data structure that lets you focus one section of the entire structure without losing the rest. Please see the last chapter of Learn You A Haskell for an intuitive approach to developing the zipper data type and functions to use on it.

Upvotes: 0

Cirdec
Cirdec

Reputation: 24166

Here's a hint: If you are at a Node x l r and you already knew that the left tree's mimSmim l was (a, l'), then the Node's mimSmim (Node x l r) would be (a, Node x l' r).

Upvotes: 3

Related Questions