URL

Minimum Depth of Binary Tree - LeetCode

Code

https://github.com/syohex/dotnet-study/tree/master/fsharp/leetcode/problems/0111/main.fsx

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

let minDepth (root: Tree) : int =
    let rec minDepth' q depth =
        match q with
        | [] -> depth
        | _ ->
            let q', ok =
                q
                |> List.fold
                    (fun (acc, ok) n ->
                        if ok then
                            acc, ok
                        else
                            match n with
                            | Leaf -> failwith "never reach here"
                            | Node(_, left, right) ->
                                match left, right with
                                | Leaf, Leaf -> acc, true
                                | Node(_), Leaf -> left :: acc, false
                                | Leaf, Node(_) -> right :: acc, false
                                | _ -> right :: left :: acc, false)
                    ([], false)

            if ok then depth else minDepth' q' (depth + 1)

    match root with
    | Leaf -> 0
    | _ -> minDepth' [ root ] 1