Minimal Tree

In [1]:

    

data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show)


    

In [2]:

    

split3 :: (Ord a) => [a] -> ([a], a, [a])
split3 [x] = ([], x, [])
split3 xs =
    let
        (left, middle : right) = splitAt (length xs `div` 2) xs
    in
        (left, middle, right)


    

In [3]:

    

minimalBST :: (Ord a) => [a] -> (Tree a)
minimalBST [] = Empty
minimalBST xs =
    let
        (left, middle, right) = split3 xs
    in
        Node middle (minimalBST left) (minimalBST right)


    

In [4]:

    

fromTree :: (Ord a) => (Tree a) -> [a]
fromTree Empty = []
fromTree (Node middle left right) =
    (fromTree left) ++ middle : (fromTree right)


    

In [5]:

    

fromTree $ minimalBST [1, 2, 3, 4, 5]


    

    






[1,2,3,4,5]

In [6]:

    

import Test.QuickCheck


    

In [7]:

    

testRoundTrip :: [Int] -> Bool
testRoundTrip xs =
    fromTree (minimalBST xs) == xs


    

In [8]:

    

quickCheck testRoundTrip


    

    






+++ OK, passed 100 tests.

In [9]:

    

height :: (Ord a) => (Tree a) -> Int
height Empty = 0
height (Node middle left right) =
    1 + max (height left) (height right)


    

In [10]:

    

testMinimalHeight :: [Int] -> Bool
testMinimalHeight xs =
    let 
        expected :: [Int] -> Int
        expected [] = 0
        expected xs = 1 + truncate (logBase 2 $ fromIntegral $ length xs)
    in
        height (minimalBST xs) == expected xs


    

In [11]:

    

quickCheck testMinimalHeight


    

    






+++ OK, passed 100 tests.

In [12]:

    

validBST :: (Ord a) => Tree a -> Bool
validBST tree =
    let
        checkNode :: (Ord a) => Tree a -> Maybe a -> Maybe a -> Bool
        checkNode Empty _ _ = True
        checkNode (Node middle left right) lower upper =
            maybe True (< middle) lower &&
            maybe True (> middle) upper &&
            checkNode left lower (Just middle) &&
            checkNode right (Just middle) upper
    in
        checkNode tree Nothing Nothing


    

In [13]:

    

validBST $ minimalBST [1, 2, 3, 4, 5]
validBST $ minimalBST [1, 2, 7, 4, 5]


    

    






True






    






False