<h2 id="heading-url">URL</h2>
<p><a target="_blank" href="https://leetcode.com/problems/unique-binary-search-trees-ii/description/">https://leetcode.com/problems/unique-binary-search-trees-ii/description/</a></p>
<h2 id="heading-code">Code</h2>
<p><a target="_blank" href="https://github.com/syohex/dotnet-study/blob/master/fsharp/leetcode/problems/0095/main.fsx">https://github.com/syohex/dotnet-study/blob/master/fsharp/leetcode/problems/0095/main.fsx</a></p>
<pre><code class="lang-plaintext">type Tree =
    | Leaf
    | Node of int * Tree * Tree

let generateTrees (n: int) : Tree list =
    let rec combinations a b acc =
        match a with
        | [] -&gt; List.rev acc
        | h :: t -&gt;
            let acc' = b |&gt; List.fold (fun acc e -&gt; (h, e) :: acc) acc
            combinations t b acc'

    let rec generateTrees' left right =
        if left &gt; right then
            [ Leaf ]
        else
            seq { left..right }
            |&gt; Seq.fold
                (fun acc n -&gt;
                    let leftTrees = generateTrees' left (n - 1)
                    let rightTrees = generateTrees' (n + 1) right

                    combinations leftTrees rightTrees []
                    |&gt; List.fold (fun acc (leftTree, rightTree) -&gt; (Node(n, leftTree, rightTree) :: acc)) acc)
                []

    generateTrees' 1 n |&gt; List.rev
</code></pre>


## URL

[https://leetcode.com/problems/unique-binary-search-trees-ii/description/](https://leetcode.com/problems/unique-binary-search-trees-ii/description/)

## Code

[https://github.com/syohex/dotnet-study/blob/master/fsharp/leetcode/problems/0095/main.fsx](https://github.com/syohex/dotnet-study/blob/master/fsharp/leetcode/problems/0095/main.fsx)

```plaintext
type Tree =
    | Leaf
    | Node of int * Tree * Tree

let generateTrees (n: int) : Tree list =
    let rec combinations a b acc =
        match a with
        | [] -> List.rev acc
        | h :: t ->
            let acc' = b |> List.fold (fun acc e -> (h, e) :: acc) acc
            combinations t b acc'

    let rec generateTrees' left right =
        if left > right then
            [ Leaf ]
        else
            seq { left..right }
            |> Seq.fold
                (fun acc n ->
                    let leftTrees = generateTrees' left (n - 1)
                    let rightTrees = generateTrees' (n + 1) right

                    combinations leftTrees rightTrees []
                    |> List.fold (fun acc (leftTree, rightTree) -> (Node(n, leftTree, rightTree) :: acc)) acc)
                []

    generateTrees' 1 n |> List.rev
```

LeetCode 95. Unique Binary Search Trees II in F#

URL

Code