Skip to content

Instantly share code, notes, and snippets.

@wavebeem
Created January 20, 2011 02:58
Show Gist options
  • Save wavebeem/787316 to your computer and use it in GitHub Desktop.
Save wavebeem/787316 to your computer and use it in GitHub Desktop.
Haskell binary search tree
module BST where
-- Define the BST data type
data BST a
= Node (BST a) (BST a) a
| Tip
deriving (Show, Eq)
-- Make a leaf node
leaf y = Node Tip Tip y
-- Adding a node to a BST
add Tip y = leaf y
add (Node left right x) y =
if y < x
then Node (add left y) right x
else Node left (add right y) x
-- Build a tree from a list
build xs = build' Tip xs
where
build' tree [] = tree
build' tree (x:xs) = build' (add tree x) xs
preOrd Tip = ""
preOrd (Node left right x) =
show x ++ " => " ++ preOrd left ++ preOrd right
inOrd Tip = ""
inOrd (Node left right x) =
inOrd left ++ show x ++ " => " ++ inOrd right
postOrd Tip = ""
postOrd (Node left right x) =
postOrd left ++ postOrd right ++ show x ++ " => "
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment