CODEWITHSUNDEEP
haskell
skills
skills

Reputation: 327

How to know maximum at an irregular tree?

I have an irregularly defined tree, how can i run through it and find the maximum value in it?

My strategy was to build a list and take out the bigger value, my problem is, i only know binary trees, where i have the left and the right, like this: Node x Empty Empty

I have this structure now:

tree= No 2 [No 3 [No 6 []], No 4 [No 7 [], No 8 []], No 5 []]

data TreeIrr a = No a [TreeIrr a]

How is it supposed to be traversed?

this is the best i could do:

maxi :: ArvIrr a -> [a]
maxi (No a []) = [a]
maxi (No a l@((No b []):z)) = [a]++[b]++(maxis l)
                    where
                     maxis ((No x k):(No y z):ls) = [y]++maxis ls
maxi (No a [k]) = [a]++(maxi k)

Upvotes: 1

Views: 295

Answers (3)

chi
chi

Reputation: 116139

Let's pretend we have a traversal function:

maxi :: ArvIrr a -> [a]

How should we extend this to a list of trees?

maxiList :: [ArvIrr a] -> [a]

Well, we could use a map:

maxiList l = map maxi l  -- WRONG type [[a]]

but we get a lists of lists instead of a single list. No problem, let's concatenate them all.

maxiList l = concat (map maxi l)

OK, now let's assume we have maxiList working, and build maxi in terms of it. This is quite simple:

maxi (No a l) = a : maxiList l

So, putting everything together:

maxi :: ArvIrr a -> [a]
maxi (No a l) = a : maxiList l
maxiList :: [ArvIrr a] -> [a]
maxiList l = concat (map maxi l)

We can further simplify it by removing maxiList and inlining it.

maxi :: ArvIrr a -> [a]
maxi (No a l) = a : concat (map maxi l)

And concat (map maxi l) can be rewritten as concatMap maxi l, exploiting the concatMap library function.

maxi :: ArvIrr a -> [a]
maxi (No a l) = a : concatMap maxi l

To compute the maximum, you can use

maxInTree :: Ord a => ArvIrr a -> a
maxInTree t = maximum (maxi t)

If you want, you can further simplify this code so that the intermediate list is not even built, and the maximum is computed directly. This is probably a bit challenging for a Haskell beginner, but it might be fun. Start by replacing concat in the code above ...

Upvotes: 3

Luis Casillas
Luis Casillas

Reputation: 30227

data TreeIrr a = No a [TreeIrr a]

The maximum element of such a tree is the maximum of two values:

  1. The element at the root note.
  2. The maximum of the maximums of its children.

Therefore:

treeMaximum :: Ord a => TreeIrr a -> a
treeMaximum (No a []) = a
treeMaximum (No a children) = max a (maximum (map treeMaximum children))

Where max :: Ord a => a -> a -> a, and maximum :: Ord a => [a] -> a are standard library functions.

Upvotes: 4

Eugene Sh.
Eugene Sh.

Reputation: 18341

Just use a simple recursive dfs-like traversal:

data TreeIrr a = No a [TreeIrr a]

findMax :: Ord a => TreeIrr a -> a
findMax (No x []) = x     -- For a tree without subtrees the maximum is it's value
findMax ( No x subtrees ) =
    maximum ( x : map findMax subtrees)      -- For a tree with subtrees the maximum is the maximum among it's root value or the maximum of it's subtrees

and then 

>> findMax (No 2 [No 3 [No 6 []], No 4 [No 7 [], No 8 []], No 5 []])
8

Upd: After a little thinking, the base case is redundant here. So just 

findMax :: Ord a => TreeIrr a -> a
findMax ( No x subtrees ) = maximum ( x : map findMax subtrees)

will work fine

Upvotes: 2

Related Questions