Paths with Sum

In [1]:

    

data Tree = Empty | Node { getValue :: Int
                         , getLeft :: Tree
                         , getRight :: Tree
                         } deriving (Show)


    

In [2]:

    

countPathsFromNode :: Tree -> Int -> Int
countPathsFromNode Empty _ = 0
countPathsFromNode (Node value left right) target =
    let
        target' = target - value
    in
        countPathsFromNode left target' +
        countPathsFromNode right target' +
            if target == value then 1 else 0

countPaths :: Tree -> Int -> Int
countPaths Empty _ = 0
countPaths node target =
    countPathsFromNode node target +
    countPaths (getLeft node) target +
    countPaths (getRight node) target


    

In [3]:

    

tree = Node 3 (Node 2 (Node 1 Empty Empty) Empty) (Node 5 (Node 4 Empty Empty) Empty)
countPathsFromNode tree 3
countPaths tree 3


    

    






1






    






2