# Binary Tree pre order transversal

I have a data type for a binary tree and a function to calculate its pre order traversal:

``````data BT a = Empty | Fork a (BT a) (BT a)
deriving (Show)

treePreOrder :: BT a -> [a]
treePreOrder Empty = []
treePreOrder (Fork x l r) =
[x] ++ treePreOrder l ++ treePreOrder r
``````

I am now trying to generate a list of all the possible trees from a pre order transversal.

``````preOrderTree :: [a] -> [BT a]
preOrderTree [] = [Empty]
preOrderTree (x:xs) =
[Fork x l r| i <- [0..length xs-1], let (ys, zs) = splitAt i xs, l <- preOrderTree ys , r <- preOrderTree zs]
``````

but it gives an empty list of trees:

``````λ> preOrderTree [1,2,3]
[]
λ> preOrderTree [1]
[]
``````

Solution

• You're close. The problem is with:

``````i <- [0..length xs-1]
``````

You have excluded `length xs`, but this is a valid split which would put all the items in the left branch.

By omitting it, you've broken the function for singletons. When you evaluate:

``````preOrderTree[1]
``````

you get `length xs-1 == -1`, so the `i <- [0..length xs-1]` generates no trees. As a result, this small error causes the entire recursion to generate no trees.

With this corrected:

``````preOrderTree :: [a] -> [BT a]
preOrderTree [] = [Empty]
preOrderTree (x:xs) =
[Fork x l r| i <- [0..length xs], let (ys, zs) = splitAt i xs
, l <- preOrderTree ys , r <- preOrderTree zs]
``````

it works fine:

``````λ> preOrderTree [1]
[Fork 1 Empty Empty]
λ> preOrderTree [1,2,3]
[Fork 1 Empty (Fork 2 Empty (Fork 3 Empty Empty)),Fork 1 Empty (Fork 2
(Fork 3 Empty Empty) Empty),Fork 1 (Fork 2 Empty Empty) (Fork 3 Empty
Empty),Fork 1 (Fork 2 Empty (Fork 3 Empty Empty)) Empty,Fork 1 (Fork 2
(Fork 3 Empty Empty) Empty) Empty]
``````