Minimum Depth of Binary Tree

Patrick Leaton
Published: March 30, 2021, 2:05 a.m.
Problem Description

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 1:

Input: root = [3,9,20,null,null,15,7]
Output: 2

Example 2:

Input: root = [2,null,3,null,4,null,5,null,6]
Output: 5

 

Constraints:

  • The number of nodes in the tree is in the range [0, 10^5].
  • -1000 <= Node.val <= 1000

 

The description was taken from https://leetcode.com/problems/minimum-depth-of-binary-tree/.

Problem Solution

#O(N) Time, O(log(N)) Space for Balanced, O(N) for Unbalanced Tree
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0
        queue = collections.deque([(root, 1)])
        while queue:
            node, depth = queue.popleft()
            if node is not None:
                if not node.left and not node.right:
                    return depth
                else:
                    queue.append((node.left, depth+1))
                    queue.append((node.right, depth+1))

Problem Explanation

The best way to solve this problem is with Breadth First Search. 

The reason why we wouldn't want to use Depth First Search is because for example, we could go deep down the right branch of the tree when the minimum depth is on the left side.  In this case, we would have wasted too much time on a traversal.

A BFS will allow us to perform a level order traversal, so that we would find the minimum depth immediately once we get to its level.

Let's first check if the root is null, if that is the case then there is no depth and we will return zero.

        if root is None:
            return 0

 

We will then initialize a queue that will contain elements with a (node, depth value) structure, then push the root node into it with the initial depth of one.

        queue = collections.deque([(root, 1)])

 

Next, we will create a loop that will run while the queue is not empty.  

        while queue:

 

During each iteration, we will pop the queue and take the node and depth values.

            node, depth = queue.popleft()

 

If our node isn't null, we will first check if it has children.

If it has no children, we are at a leaf node.  The first leaf node we find will have the minimum depth, so we will return the depth that was popped the queue.

            if node is not None:
                if not node.left and not node.right:
                    return depth

 

If the node still has children, we will push both children onto the queue and increment the depth by one.

                else:
                    queue.append((node.left, depth+1))
                    queue.append((node.right, depth+1))

 

We will continue to do this iteratively until we get to a leaf node, then return the minimum depth.