111. Minimum Depth of Binary Tree

Summary

Given a binary tree, find its minimum depth.

Approach

BFS.

As soon as we find the first leaf node, we can stop the traversal and return the current depth.

Function

Initialization:

nodes = [root]
depth = 1

If root is None: return 0

While nodes is not empty: new_nodes = [] For n in nodes: If n.left is None and n.right is None: return depth If n.left: new_nodes.append(n.left) If n.right: new_nodes.append(n.right)

If new_nodes: depth += 1 nodes = new_nodes

Complexity

Time Complexity: O(N) Space Complexity: O(N)