sumTree.hs

{-# LANGUAGE MultiWayIf #-}

-- http://codercareer.blogspot.com/2013/03/no-46-nodes-with-sum-in-binary-search.html

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

getValue (Leaf v) = v
getValue (Branch v _ _) = v

type Path a = [a]

findSum :: (Num a, Ord a) => a -> Tree a -> [Path a]
findSum s = fs 0 []
  where
    fs prevSum path tree =
      let v = getValue tree
          newSum = prevSum + v
          newPath = path ++ [v]
      in if | newSum == s -> [newPath] -- if the new sum matches, we are done
            | newSum >  s -> [] -- invalid, the sum went over
            | newSum <  s ->
              case tree of
                Leaf v -> [] -- we reached a leaf, we are done
                Branch v l r -> fs newSum newPath l ++ fs newSum newPath r