Skip to content

Instantly share code, notes, and snippets.

@adpoe
Created June 16, 2016 05:30
Show Gist options
  • Save adpoe/c062f370868c7e1e9d7318847496d192 to your computer and use it in GitHub Desktop.
Save adpoe/c062f370868c7e1e9d7318847496d192 to your computer and use it in GitHub Desktop.
Haskell Binary Tree Traversals
-- Do Tree Traversals and Built a Visitation List for each
preorder :: BinaryTree a -> [a]
preorder Leaf = []
preorder (Node left root right) = root : preorder left ++ preorder right
-- NOTE: Need to use the ++ so each list gets built separately and then concatenated
-- after it hits bottom
inorder :: BinaryTree a -> [a]
inorder Leaf = []
inorder (Node left root right) = inorder left ++ [root] ++ inorder right
-- NOTE: Need to put root in its own list so we can concatenate
postorder :: BinaryTree a -> [a]
postorder Leaf = []
postorder (Node left root right) = postorder left ++ postorder right ++ root : []
-- Similarly, here. Need to Cons root onto a list, since it'll be the bottom value
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment