Haskell binary tree max int?

0
votes

I'm trying to write a haskell function that will return the max int inside a binary tree of integers. My binary tree is defined as follows:

data Tree = Node Int Tree Tree | Leaf Int
deriving (Eq,Show)

The way I understand it this declaration is saying that for the 'Tree' data type, it can either be a single leaf int, or be a subtree containing two more trees. So my maxInt function will look something like this ( I think )

maxInt :: Tree -> Int      --maxInt function receives Tree, returns int
maxInt --something to detect if the Tree received is empty 
--if only one node, return that int
--look through all nodes, find largest

and so when my function is given something like maxInt (Node 5 (Leaf 7) (Leaf 2)) , the correct value for maxInt to return would be 7.

I'm new to haskell and don't really know where to start with this problem, I would really appreciate some guidance. Thank you

2
haskellfunctional-programmingbinary-tree
Are you familiar with pattern matching yet? If so, what are some ways you might match on a Tree value? – David Young
Well how would you define it in words? What is the maximum of a Tree (without the Haskell syntax). – Willem Van Onsem
@WillemVanOnsem I would first check that the node is not null. Then get two ints, left_max and right_max that call the function recursively like so: int left_max = findmax(root.left) and right_max = findmax(root.left) . int max would be set to whichever one of these values is larger. If the current int value of the root passed into findmax() is greater than int max, then max will be set = root.intvalue. At the end of the function, int max will be returned. – Martin
You've tagged this binary-search-tree. Is this actually a binary search tree? If so, there's a bunch faster way to get the maximum! Your example suggests it's not, in which case you should remove that tag. – dfeuer
My question was for a binary tree, not a binary search tree. I know that if it was a bst I could just get the furthest left node. I'll remove the tag – Martin

2 Answers

4
votes

Let me start it for you:

maxInt :: Tree -> Int
maxInt (Leaf x) = ?
maxInt (Node x l r) = ?

You may find it helpful to use the standard function max, which takes two arguments and returns their maximum:

max 3 17 = 17
2
votes

To begin with, we have this datatype:

data Tree = Node Int Tree Tree | Leaf Int
  deriving (Eq,Show)

That means, we have two constructors for things of type Tree: either we have a Leaf with a single Int value, or we have a Node which allows us to represent bigger trees in a recursive fashion.

So, for example we can have these trees:

Leaf 0

And more complex ones:

Node 3 (Leaf 0) (Leaf 4)

Recall that this tree representation have information both in the leaves and in the nodes, so for our function we will need to take that into account.

You guessed correctly the type of the function maxInt, so you are halfway through!

In order to define this function, given we have a custom defined datatype, we can be confident in using pattern-matching.

Pattern-matching is, putting it simple, a way to define our functions by equations described by, on the left side, one element of our datatype (either Leaf or Node, in our case) and on the right side, the result value. I'd recommend you to learn more about pattern-matching here: pattern matching in Haskell

Hence, we start our function by its type, as you correctly guessed:

maxInt :: Tree -> Int

As we have seen earlier, we will use pattern-matching for this. What would be the first equation, that is, the first pattern-matching case for our function? The simplest tree we have given our datatype is Leaf value. So we start with:

maxInt (Leaf n) = n

Why n as a result? Because we don't have any other value than n in the tree and therefore it's the maximum.

What happens in a more complex case?

maxInt (Node n leftTree rightTree) = ...

Well... we can think that the maximum value for the tree (Node n leftTree rightTree) would be the maximum among n, the maximum value of leftTree and rightTree.

Would you be encouraged to write the second equation? I strongly recommend you to first read the chapter of the book I just linked above. Also, you might want to read about recursion in Haskell.