Tree.hs

module Data.Tree where

data BinTree a
  = Leaf
  | Branch
    { binTreeLeft :: BinTree a
    , binTreeNode :: a
    , binTreeRight :: BinTree a
    }
  deriving (Show, Read, Eq, Ord)

data BstRange a
  = BstRange
    { bstMin :: a
    , bstMax :: a
    }
  deriving (Show, Eq)

data NotBst = NotBst deriving (Show, Eq)

ensureBst :: Ord a => BinTree a -> Either NotBst (Maybe (BstRange a))
ensureBst Leaf = Right Nothing
ensureBst (Branch l x r) = case (minResult, maxResult) of
  (Right minX, Right maxX) -> Right (Just (BstRange minX maxX))
  _ -> Left NotBst
  where
    minResult = case ensureBst l of
      Right (Just rangeL)
        | bstMax rangeL < x -> Right (bstMin rangeL)
        | otherwise -> Left NotBst
      Right Nothing -> Right x
      Left err -> Left err
    maxResult = case ensureBst r of
      Right (Just rangeR)
        | bstMin rangeR > x -> Right (bstMax rangeR)
        | otherwise -> Left NotBst
      Right Nothing -> Right x
      Left err -> Left err