Instantly share code, notes, and snippets.

# remko/mergebst.hs Created Dec 1, 2012

What would you like to do?
Merge Binary Search Trees
 import Data.List import Data.Array data Tree a = Leaf | Node a (Tree a) (Tree a) deriving (Show, Eq) -- Flatten a Binary Search Tree into a sorted list flatten :: Tree a -> [a] flatten Leaf = [] flatten (Node n l r) = (flatten l) ++ n : flatten r -- Merge Binary Search Trees into a list mergeBSTToList :: Ord a => Tree a -> Tree a -> [a] mergeBSTToList tree1 tree2 = merge (flatten tree1) (flatten tree2) where merge n [] = n merge [] n = n merge (x:xs) (y:ys) | x < y = x : merge xs (y:ys) | otherwise = y : merge (x:xs) ys -- Merge Binary Search Trees to output mergeBSTToIO :: (Ord a, Show a) => Tree a -> Tree a -> IO () mergeBSTToIO tree1 tree2 = mapM_ print \$ mergeBSTToList tree1 tree2 -- Merge Binary Search Trees into a new tree mergeBSTToBST :: Ord a => Tree a -> Tree a -> Tree a mergeBSTToBST tree1 tree2 = makeTree \$ mergeBSTToList tree1 tree2 -- Create a Binary Search Tree out of a sorted list -- Using an array for lower algorithmic complexity. makeTree :: [a] -> Tree a makeTree l = makeTree' (listArray (0, length l - 1) l) 0 (length l) where makeTree' a low high | low == high = Leaf | otherwise = Node (a!split) (makeTree' a low split) (makeTree' a (split+1) high) where split = low + (high - low) `div` 2