Problem 61a

Count the leaves of a binary tree. The leaves are the nodes that have empty nodes in both their right and left subtrees.

Example

tree = Tree 1 (Tree 2 Empty (Tree 4 Empty Empty))
                 (Tree 2 Empty Empty)

countLeaves tree == 2

Unit Test

import Html
import List


type Tree a
    = Empty
    | Node a (Tree a) (Tree a)


countLeaves : Tree a -> Int
countLeaves tree =
    -- your implementation here
    0


main =
    Html.text
        (if (test) then
            "Your implementation passed all tests."
         else
            "Your implementation failed at least one test."
        )


test : Bool
test =
    List.all ((==) True)
        [ countLeaves Empty == 0
        , countLeaves (Node 1 Empty Empty) == 1
        , countLeaves (Node 1 (Node 2 Empty Empty) Empty) == 1
        , countLeaves (Node 1 (Node 2 Empty Empty) (Node 0 Empty Empty)) == 2
        , countLeaves (Node 1 (Node 2 Empty Empty) (Node 0 Empty Empty)) == 2
        ]

Hints

1. You should be pretty good at recursion by now.

Solutions

Solutions