LeetCode Patterns Adventure 21 — Minimum Depth of Binary Tree

I will be chronicling my journey through Sean Prashed’s excellent LeetCode Patterns from Easy to Hard using my trusty programming language Python. Today we will be tackling the Minimum Depth of Binary Tree question from LeetCode. As always, this is a solution and not the solution. The beauty of programming is that there are many approaches to the same result.

Task: 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.

Solution Code

Runtime Complexity: O(V) where V is the number of nodes

Leetcode Performance

We will be using a modified depth-first search algorithm for our solution. Intuitively this makes sense as we are looking for the depth of the tree. We will be using recursion to keep track of the previous depth and at each recursion, we will increase the depth by 1 as we are calling DFS again on a child node if it exists.

In our recursion we will handle four different cases:

1. Both left and right child nodes are null. This means that our current node is a leaf and we just return the new_depth.
2. The left child node is null while the right child node exists. This means that we will have to continue down our depth calculation only through the right child.
3. The right child node is null while the left child node exists. This means that we will have to continue down our depth calculation only through the left child.
4. Both left and right child nodes exist. In this case we will recurse through both left and right child to obtain their minimum depth each. We will then return the depth from the left and right child that is smaller.

Our minimum depth will propagate upwards through our recursion to the minDepth function. We then simply return this value.

Source Code: https://github.com/evangelato/LeetcodePatternsAdventure/blob/main/Easy/111_minimum_depth_of_binary_tree.py