findClosest.hs

{-# LANGUAGE MultiWayIf #-}

-- http://codercareer.blogspot.com/2013/03/no-45-closest-node-in-binary-search-tree_2.html

data BTree a = Nil | Leaf a | Node a (BTree a) (BTree a)

-- | Given an /a/, find the node whose value is closest to the given /a/.
findClosest :: (Num a, Ord a) => a -> BTree a -> a
findClosest _ Nil = error "Empty tree"
findClosest _ (Leaf v) = v -- If we a given a single node tree, the value
                           -- is the closest, regardless of the input
findClosest a (Node v l r) =
  let base = (v, abs $ a - v)
  in if | a == v -> v
        | a > v -> go base r
        | otherwise -> go base l
  where
    -- given two diffs with their values, get the one with the smallest
    -- diff
    minOnDiff t1@(_, d1) t2@(_, d2)
      | d1 <= d2 = t1
      | otherwise = t2

    go oldBase t =
      let newBase v = minOnDiff oldBase (v, abs $ a - v)
      in case t of
           Nil -> fst oldBase -- we reached the end, the last value is the
                              -- closest one
           Leaf v -> fst $ newBase v -- We reached a leaf, compare it one more
                                     -- time and return
           Node v l r ->
            if | a == v    -> v
               | a > v     -> go (newBase v) r
               | otherwise -> go (newBase v) l