BST Sequences



In [1]:

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



In [2]:

    
{-# LANGUAGE ScopedTypeVariables #-}



In [3]:

    
import Data.List (foldl')



In [4]:

    
makeBST :: forall a. Ord a => [a] -> Tree a
makeBST xs = foldl' insert Empty xs
    where
        insert :: Tree a -> a -> Tree a
        insert Empty x = Node x Empty Empty
        insert (Node y left right) x
            | x > y = Node y left (insert right x)
            | otherwise = Node y (insert left x) right



In [5]:

    
makeBST [2, 1, 3]
makeBST [2, 3, 1]









    





Node 2 (Node 1 Empty Empty) (Node 3 Empty Empty)






    





Node 2 (Node 1 Empty Empty) (Node 3 Empty Empty)



In [6]:

    
mix :: [a] -> [a] -> [[a]]
mix xs [] = [xs]
mix [] ys = [ys]
mix (x:xs) (y:ys) = map (x:) (mix xs (y:ys)) ++ map (y:) (mix (x:xs) ys)



In [7]:

    
mix [1, 2] [3, 4]









    





[[1,2,3,4],[1,3,2,4],[1,3,4,2],[3,1,2,4],[3,1,4,2],[3,4,1,2]]



In [8]:

    
bstSequences :: Tree a -> [[a]]
bstSequences Empty = [[]]
bstSequences (Node value left right) =
     map (value:) $ concat [mix l r | l <- sequencesLeft, r <- sequencesRight]
        where
            sequencesLeft = bstSequences left
            sequencesRight = bstSequences right



In [9]:

    
bstSequences $ makeBST [2, 1, 3]
bstSequences $ makeBST [3, 2, 1, 5, 4]









    





[[2,1,3],[2,3,1]]






    





[[3,2,1,5,4],[3,2,5,1,4],[3,2,5,4,1],[3,5,2,1,4],[3,5,2,4,1],[3,5,4,2,1]]

Tests



In [10]:

    
import Test.QuickCheck



In [11]:

    
testBSTSequences :: [Int] -> Bool
testBSTSequences xs =
    all ((== bst) . makeBST) $ bstSequences bst
        where
            bst = makeBST xs



In [12]:

    
quickCheckWith stdArgs { maxSize = 15 } testBSTSequences









    





+++ OK, passed 100 tests.