LeetCode Entry

111. Minimum Depth of Binary Tree

11.07.2023 easy 2023 kotlin

Count nodes in the shortest path from root to leaf

111. Minimum Depth of Binary Tree easy blog post substack image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/271

Problem TLDR

Count nodes in the shortest path from root to leaf

Intuition

  • remember to count nodes, not edges
  • leaf is a node without children
  • use BFS or DFS

Approach

Let’s use BFS

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(n)\)

Code


fun minDepth(root: TreeNode?): Int = with(ArrayDeque<TreeNode>()) {
    root?.let { add(it) }
    generateSequence(1) { (it + 1).takeIf { isNotEmpty() } }
    .firstOrNull {
        (1..size).any {
            with(poll()) {
                left?.let { add(it) }
                right?.let { add(it) }
                left == null && right == null
            }
        }
    } ?: 0
}