MinimumDepthOfBinaryTree.swift

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */

extension TreeNode {
    var isLeaf: Bool {
        return left == nil && right == nil
    }
    
    var validSubtrees: [TreeNode] {
        return [left, right].compactMap { $0 }
    }
}

class Solution {
    func minDepth(_ node: TreeNode?) -> Int {
        return minDepthRecursive(node)
    }
    
    func minDepthIterative(_ node: TreeNode?) -> Int {
        guard let node = node else {
            return 0
        }
        
        var queue = [(depth: 1, node: node)]
        var depth = 0
        
        while let nodeInfo = queue.first {            
            queue.removeFirst()
            
            if nodeInfo.node.isLeaf {
                depth = nodeInfo.depth
                break
            }
         
            let validSubtrees = nodeInfo.node.validSubtrees
            queue.append(contentsOf: validSubtrees.map { (depth: nodeInfo.depth + 1, node: $0) } )
        }
        
        return depth
    }
    
    func minDepthRecursive(_ node: TreeNode?) -> Int {
        guard let node = node else {
            return 0
        }
                
        guard node.isLeaf == false else {
            return 1
        }
        
        // If we only have one valid subtree - recurse on only that one.
        let validSubtrees = node.validSubtrees
        if validSubtrees.count == 1, let validSubtree = validSubtrees.first {
            return 1 + minDepth(validSubtree)
        }

        // Both subtrees are valid - recurse on both.
        // I originally had only this recursive call - but then realized that in the case of an invalid subtree, minDepth returns 0... 
        // and min(0, ...) would always return 0.
        
        return 1 + min(minDepth(node.left), minDepth(node.right))
    }
}