CODEWITHSUNDEEP
haskell
user11340751
user11340751

Reputation:

Postorder traversal of binary tree with recursive data type

I'm trying to create a function for a post-order traversal of a recursive data type that creates an binary tree where the examples could create as many child leafs as possible. I've tried to set the nodes to left:root:right but the error doesn't recognize them - however, it would recognize (y:ys). It also recognizes root as an Int no matter if I use () or [] or nothing around it. What am I missing?

This is the data type and some easy examples to test it with:

data BiTree a = L a
            | N [BiTree a]

ex1 :: BiTree Int
ex1 = N [(L 1),(L 1),(L 3)]

ex2 :: BiTree Int
ex2 = N [(L 1),(N[(L 2),(L 3)]),(L 4)]

Here's the code I wrote:

postord :: BiTree a -> [Int]
postord (L x)                  = [x]
postord (N (left:root:right))  = postord (N right) ++ postord (N left) ++ [root]

Here's the error:

* Couldn't match expected type `Int' with actual type `BiTree a'
* In the expression: root
  In the second argument of `(++)', namely `[root]'
  In the second argument of `(++)', namely
    `postord (N left) ++ [root]'
* Relevant bindings include
    right :: [BiTree a] (bound at try.hs:21:23)
    root :: BiTree a (bound at try.hs:21:18)
    left :: BiTree a (bound at try.hs:21:13)
    postord :: BiTree a -> [Int] (bound at try.hs:20:1)
|
21 | postord (N (left:root:right)) = postord (N right) ++ postord (N left) ++ [root]
|                                                         ^^^^

I don't understand why left:right:root won't bind, and why recalling postord in the list with appends won't compile a list of every node within the right node, left node, and root as it is.

Upvotes: 0

Views: 185

Answers (2)

nemron
nemron

Reputation: 731

Don't know if I understood your question, but what about this:

postord :: BiTree a -> [a]
postord (L x) = [x]
postord (N cs) = concatMap postord cs

Upvotes: 0

chepner
chepner

Reputation: 530940

N doesn't have specific left and right children, and it certainly doesn't have any distinguished root value; it just has an arbitrary list of children.

You BiTree only stores values in the leaves. The only thing to do with an N value is map postord on to each child, and concatenate the results into a single list. (As such, there's no real difference between the pre-, in-, and post-order traversals.)

postord :: BiTree a -> [a]
postord (L x)         = [x]
postord (N children)  = concatMap postord children

Now, if you had a type that did store values in the internal nodes, your type might look like

data BiTree a = L a | N a [BiTree a]

Then your post-order traversal would have to account for the value stored in an internal node, similar to your previous attempt.

postord :: BiTree a -> [a]
postord (L x) = [x]
postord (N v children) = concatMap postord children ++ [v]

Appending a single value to a longer list isn't ideal, but that's a problem for another question.

Upvotes: 1

Related Questions