# [Haskell-cafe] Construct all possible trees

Mirko Rahn rahn at ira.uka.de
Wed Jun 13 07:45:44 EDT 2007

```Andrew Coppin wrote:

> such that all_trees [1,2,3] will yield

> [
> Leaf 1,
> Leaf 2,
> Leaf 3,
> Branch (Leaf 1) (Leaf 2),
> Branch (Leaf 1) (Leaf 3),
> Branch (Leaf 2) (Leaf 1),
> Branch (Leaf 2) (Leaf 3),
> Branch (Leaf 3) (Leaf 1),
> Branch (Leaf 3) (Leaf 2),
> Branch (Branch (Leaf 1) (Leaf 2)) (Leaf 3),
> Branch (Branch (Leaf 1) (Leaf 3)) (Leaf 1),
> Branch (Branch (Leaf 2) (Leaf 1)) (Leaf 3),
> Branch (Branch (Leaf 2) (Leaf 3)) (Leaf 1),
> Branch (Branch (Leaf 3) (Leaf 1)) (Leaf 2),
> Branch (Branch (Leaf 3) (Leaf 2)) (Leaf 1),
> Branch (Leaf 1) (Branch (Leaf 2) (Leaf 3)),
> Branch (Leaf 1) (Branch (Leaf 3) (Leaf 2)),
> Branch (Leaf 2) (Branch (Leaf 1) (Leaf 3)),
> Branch (Leaf 2) (Branch (Leaf 3) (Leaf 2)),
> Branch (Leaf 3) (Branch (Leaf 1) (Leaf 2)),
> Branch (Leaf 3) (Branch (Leaf 2) (Leaf 1))
> ]

Just another way (assuming the given order is not relevant), based on
the idea that it is quite easy to insert a new node on all possible
positions in an already existing tree.

data Tree a = Leaf a | Branch (Tree a) (Tree a) deriving Show

decomp (Branch l r) = [(l,flip Branch r),(r,Branch l)]
decomp _            = []

insert x t = Branch x t
: Branch t x
: [re b | (part,re) <- decomp t, b <- insert x part]

all_trees []     = []
all_trees (x:xs) =
let this = Leaf x
more = all_trees xs
in this : more ++ concatMap (insert this) more

/BR

--
-- Mirko Rahn -- Tel +49-721 608 7504 --
--- http://liinwww.ira.uka.de/~rahn/ ---
```