Skip to content

Instantly share code, notes, and snippets.

@remko
Created December 1, 2012 08:30
Show Gist options
  • Save remko/4181097 to your computer and use it in GitHub Desktop.
Save remko/4181097 to your computer and use it in GitHub Desktop.
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment