haskelltreebinary-tree# 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]
```

- Comparing lists in Haskell
- Is there a non-identity monad morphism M ~> M that is monadically natural in M?
- Problem with loading module ‘Distribution.Simple’
- Improving efficiency in Stirling numbers calculation
- Does sequencing an infinite list of IO actions by definition result in a never-ending action? Or is there a way to bail out?
- How to call pgQuery from postgresql-query?
- How to avoid whitespace after a tag (link) in Hamlet templates?
- Understanding type-directed resolution in Haskell with existential types
- Why is seq bad?
- Understanding bind function in Haskell
- How to create route that will trigger on any path in Servant?
- How do I use a global state in WAI middleware?
- nixos 23.11 cabal install mysql-simple problem - "Missing (or bad) C libraries"
- Is there a way to kill all forked threads in a GHCi session without restarting it?
- Why can an invalid list expression such as 2:1 be assigned to a variable, but not printed?
- Iterate over a type level list and call a function based on each type in the list
- How does this solution of Project Euler Problem 27 in the Haskell Wiki work?
- Why `Monad` is required to use `pure`?
- Can't do partial function definitions in GHCi
- recommended way to convert Double -> Float in Haskell
- Haskell profiling understanding cost centre summary for anonymous lambda
- Why is Haskell fully declarative?
- GHC Generating Redundant Core Operations
- Question about Event firing in reflex-frp
- Using Haskell's "Maybe", type declarations
- How can I elegantly invert a Map's keys and values?
- Why there is no output for wrapped IO in Haskell?
- What are the definitions of Weather and Memory in xmobar repo?
- Serializing a Data.Text value to a ByteString without unnecessary \NUL bytes
- Using Haskell with VS Code