Merge Binary Search Trees

mergebst.hs

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