Minimum Depth of Binary Tree

Tree BFS

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.

• When we come across a leaf node, then this level will represent the minimum depth

Solution

from collections import deque
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0
        
        queue = deque()
        queue.append(root)
        count = 0
        while queue:
            count+=1
            levelSize = len(queue)
            
            for _ in range(levelSize):
                currentNode = queue.popleft()
                
                if not currentNode.left and not currentNode.right:
                    return count
                else:
                    if currentNode.left:
                        queue.append(currentNode.left)
                    if currentNode.right:
                        queue.append(currentNode.right)
                        
        return count
        
#Time: O(n)
#Space: O(1)