# How to define listTree so that it runs in linear time?

``````listTree' :: Tree a -> [a]
listTree' t = foldTree f z t []
where
f = undefined
z [] = []
``````

Need help solving for f. when I insert `f a b c = a ++ [b] ++ c` I get an error

``````data Tree a
= Tip
| Bin (Tree a) a (Tree a)
deriving (Show, Eq)

foldTree :: (b -> a -> b -> b) -> b -> Tree a -> b
foldTree f z Tip         = z
foldTree f z (Bin l x r) = f (foldTree f z l) x (foldTree f z r)
``````

here is foldTree and data type for tree

### >Solution :

In order to achieve linear time, you should let `foldTree f z t` return a function that takes a list and returns a list.

This means that for `z`, a leaf, we simply return the given list, and we thus do not prepend any value. For `f` we will take the list, call it with the right subtree, then prepend that list with the value of that `Bin` node, and finally call it with the left subtree, so:

``````listTree' :: Tree a -> [a]
listTree' t = foldTree f id t []
where f x y z ls = x (y: z ls)``````

Here `ls` is thus the list we need to process, `z` is a function to prepend the items of the right subtree to `ls`, `y` is the value stored in that node, and `x` is a function that prepends the items of the left subtree to the list.

We can define `f`, as @chi says as `f x y z = x . (y:) . z`. We thus first apply the function generated for the right subtree, then prepend the list with `y`, and then run it through the function of the left subtree.