CODEWITHSUNDEEP
haskelltree
Adriana
Adriana

Reputation: 91

Haskell traverse tree inorder preorder postorder

I have the following Haskell data definition:

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

and I wrote the following programs to traverse trees preorder, inorder and postorder:

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]

The error that I get is:

- Type error in application  
*** Expression     : preorder t0 ++ preorder t1  
*** Term           : preorder t1  
*** Type           : Int  
*** Does not match : [a]

I need to return a list that contains all tree integers in appropriate order. Any help is highly appreciated as I am new to Haskell.

Upvotes: 4

Views: 13192

Answers (3)

Ondřej Šebek
Ondřej Šebek

Reputation: 27

Changing the functions fixes the error, but you can only insert elements in pairs into your Tree.

Better change it to:

data Tree = Leaf | Branch Int Tree Tree deriving Show

inorder Leaf = []
inorder (Branch n left right) = inorder left ++ [n] ++ inorder right
-- etc.

Nice page to check out algorithm implementations in different languages is Rosetta Code which has a page on Tree traversals including in Haskell.

Upvotes: 2

Adriana
Adriana

Reputation: 91

The error is:

preorder(Leaf n) = n

Should be:

preorder(Leaf n) = [n]

And same for inorder and postorder.

Upvotes: 5

geekosaur
geekosaur

Reputation: 61467

You're returning Int from the base case but [Int] from the constructive case. The leaves should be lists too.

Upvotes: 6

Related Questions