CODEWITHSUNDEEP
haskellrecursionpattern-matching
Erdnussflip007
Erdnussflip007

Reputation: 23

How do I read what's in a binary tree in Haskell?

I have the following type:

data Tree = Branch (Tree) (Tree) | Leaf Int deriving(Show)

now I want to create a function that gives the highest value leaf in the tree. But I am stuck, because I don't know how to get the two following trees of a given tree.

For example I have a tree a that looks like this: let a = Branch (Leaf 10) (Leaf 2)

How do I read the Leaf with value 10 in another function?

Upvotes: 1

Views: 161

Answers (2)

Chris
Chris

Reputation: 36680

When dealing with recursion, you need to keep in mind a base case.

For:

data Tree = Branch (Tree) (Tree) | Leaf Int deriving(Show)

Your base case is Leaf Int. The maximum value of a leaf is very simply the value held by that leaf.

maxTree :: Tree -> Int
maxTree (Leaf n) = n

Now, how do you deal with a Branch? What is a Branch? It's basically two more Trees.

Consider a very simple Tree:

   Branch
    /  \
   /    \
  /      \
Leaf 1   Leaf 4

The max value is obviously 4. Why? Because the maxTree computation on the right branch was bigger than the maxTree calculation on the left branch.

Consider a more complex Tree:

   Branch
    /  \
   /    \
  /      \
Leaf 1   Branch
          / \
         /   \
        /     \
     Branch   Leaf 8
      / \
     /   \
    /     \
  Leaf 3  Leaf 9

The answer is obviously 9. How do we know this? Well, maxTree tells us the maximum value of Leaf 1 is 1. Each Branch's max value is computed by figuring out the maximum value of the left and right branches. If we call maxTree recursively on each Branch eventually we compare 3 to 9. Clearly 9 is bigger. Now we're comparing 9 to 8. 9 is again bigger. And then 9 to 1, and 9 wins out again.

Now you just need to translate that into code.

maxTree :: Tree -> Int
maxTree (Leaf n) = n
maxTree (Branch left right) = ...

Note that all of this becomes much easier if we're not just talking about a binary tree, but a binary search tree with a strict ordering invariant.

Upvotes: 7

Daniel Wagner
Daniel Wagner

Reputation: 153342

A typical skeleton looks like this:

maxTree :: Tree -> Int
maxTree (Branch x y) = {- TODO -}
maxTree (Leaf n) = {- TODO -}

Upvotes: 6

Related Questions