Tree Traversal in Haskell

Question

Here is a peice of code to traverse a tree which is not working:

data Tree = Leaf Int | Node Int Tree Tree deriving Show 

preorder(Leaf n) = [n]
preorder(Node n t0 t1) = [n] ++ (preorder t0) ++ (preorder t1)

inorder(Leaf n) = [n]
inorder(Node n t0 t1) = (inorder t0) ++ [n] ++ (inorder t1)

postorder(Leaf n) = [n]
postorder(Node n t0 t1) = (postorder t0) ++ (postorder t1) ++ [n]

I have been asked to execute the following:

Node 8 (Node 3 (Leaf 5) (Leaf 2)) (Node 1 (Leaf 9) (Leaf 6))

When I execute the above statement it returns back as it is, when it should return:

preorder t = [8,3,5,2,1,9,6]

inorder t = [5,3,2,8,9,1,6]

postorder t =[5,2,3,9,6,1,8]

How can I fix this?

Answer 1

What you have given:

Node 8 (Node 3 (Leaf 5) (Leaf 2)) (Node 1 (Leaf 9) (Leaf 6))

is a value of type Tree. You can give this value a name by creating a binding or definition for it. If you're working in a source file, you can just do

myTree = Node 8 (Node 3 (Leaf 5) (Leaf 2)) (Node 1 (Leaf 9) (Leaf 6))

or give it a type signature:

myTree :: Tree  -- this is the type signature
myTree = Node 8 (Node 3 (Leaf 5) (Leaf 2)) (Node 1 (Leaf 9) (Leaf 6))

If you're working in the interpreter, ghci, you can use let to create a new definition:

Prelude> let myTree = Node 8 (Node 3 (Leaf 5) (Leaf 2)) (Node 1 (Leaf 9) (Leaf 6))

Your task seems to be to evaluate each of the functions postorder, inorder and preorder when given this tree. If you're in a source file, you'll want to save the result in a definition:

inOrderResult :: [Int]
inOrderResult = inorder myTree

(Note that we passed in myTree as an argument to the function inorder.) And if you're working with ghci, just typing

Prelude> inorder myTree

will print the result to the terminal.