<h2 id="heading-url">URL</h2>
<p><a target="_blank" href="https://leetcode.com/problems/check-completeness-of-a-binary-tree/description/">Check Completeness of a Binary Tree - LeetCode</a></p>
<h2 id="heading-code">Code</h2>
<p><a target="_blank" href="https://github.com/syohex/dotnet-study/tree/master/fsharp/leetcode/problems/0958/main.fsx">https://github.com/syohex/dotnet-study/tree/master/fsharp/leetcode/problems/0958/main.fsx</a></p>
<pre><code class="lang-plaintext">type Tree =
    | Leaf
    | Node of int * Tree * Tree

let isCompleteTree (root: Tree) : bool =
    let rec countNodes node =
        match node with
        | Leaf -&gt; 0
        | Node(_, left, right) -&gt; 1 + (countNodes left) + (countNodes right)

    let rec isCompleteTree' q nodes =
        match q with
        | [] -&gt; true
        | _ -&gt;
            let valid =
                q
                |&gt; List.forall (fun (node, index) -&gt;
                    match node with
                    | Leaf -&gt; true
                    | _ -&gt; index &lt;= nodes)

            if valid then
                let q' =
                    q
                    |&gt; List.fold
                        (fun acc (node, index) -&gt;
                            match node with
                            | Leaf -&gt; acc
                            | Node(_, left, right) -&gt; (left, 2 * index) :: (right, 2 * index + 1) :: acc)
                        []

                isCompleteTree' q' nodes
            else
                false

    isCompleteTree' [ (root, 1) ] (countNodes root)
</code></pre>


## URL

[Check Completeness of a Binary Tree - LeetCode](https://leetcode.com/problems/check-completeness-of-a-binary-tree/description/)

## Code

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

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

let isCompleteTree (root: Tree) : bool =
    let rec countNodes node =
        match node with
        | Leaf -> 0
        | Node(_, left, right) -> 1 + (countNodes left) + (countNodes right)

    let rec isCompleteTree' q nodes =
        match q with
        | [] -> true
        | _ ->
            let valid =
                q
                |> List.forall (fun (node, index) ->
                    match node with
                    | Leaf -> true
                    | _ -> index <= nodes)

            if valid then
                let q' =
                    q
                    |> List.fold
                        (fun acc (node, index) ->
                            match node with
                            | Leaf -> acc
                            | Node(_, left, right) -> (left, 2 * index) :: (right, 2 * index + 1) :: acc)
                        []

                isCompleteTree' q' nodes
            else
                false

    isCompleteTree' [ (root, 1) ] (countNodes root)
```

LeetCode 958. Check Completeness of a Binary Tree in F#

URL

Code