Minimum Depth of Binary Tree (in Python)

Problem

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its minimum depth = 2.

Solution

Approach 1 : Recursion

class Solution:
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root: 
            return 0 
        
        children = [root.left, root.right]
        # if we're at leaf node
        if not any(children):
            return 1
        
        min_depth = float('inf')
        for c in children:
            if c:
                min_depth = min(self.minDepth(c), min_depth)
        return min_depth + 1 

Complexity analysis

•Time complexity : we visit each node exactly once, thus the time complexity is \(O(N)\), where N is the number of nodes.

•Space complexity : in the worst case, the tree is completely unbalanced, e.g. each node has only one child node, the recursion call would occur N times (the height of the tree), therefore the storage to keep the call stack would be \(O(N)\). But in the best case ( the tree is completely balanced), the height of the tree would be log(N). Therefore, the space complexity in this case would be \O(logN\).

Approach 3: BFS Iteration

The drawback of the DFS approach in this case is that all nodes should be visited to ensure that the minimum depth would be found. Therefore, this results in a \(O(N)\) complexity. One way to optimize the complexity is to use the BFS strategy. We iterate the tree level by level, and the first leaf we reach corresponds to the minimum depth. As a result, we do not need to iterate all nodes.

from collections import deque
class Solution:
    def minDepth(self, root):
        if not root :
            return 0
        else :
            node_deque = deque([(1, root),])
 
        while node_deque:
            depth, root = node_deque.popleft()
            children = [root.left, root.right]
            if not any(children):
                return depth
            for c in children :
                if c:
                    node_deque.append((depth+1, c))
 

Complexity analysis

•Time complexity : in the worst case for a balanced tree we need to visit all nodes level by level up to the tree height, that excludes the bottom level only. This way we visit N/2 nodes, and thus the time complexity is O(N).

•Space complexity : is the same as time complexity here O(N).

Source

https://leetcode.com/problems/minimum-depth-of-binary-tree/