Skip to content

Instantly share code, notes, and snippets.

Created June 16, 2016 05:30
  • Star 3 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
What would you like to do?
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