Leetcode – Minimum Depth of Binary Tree in Python

Spread the love

Introduction

Binary trees are one of the most fundamental data structures in computer science, and they form the basis for more advanced data structures such as binary search trees, heaps, and several others. The Minimum Depth of Binary Tree problem is a classic example of a problem that tests a candidate’s ability to work with binary trees. In this comprehensive article, we will explore various methods to solve the Minimum Depth of Binary Tree problem on LeetCode using Python.

Understanding the Problem

Before diving into the solutions, let’s first understand the problem statement. The Minimum Depth of Binary Tree problem asks you to find the minimum depth of a binary tree. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. A leaf is a node with no children.

For example, consider the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

The minimum depth of this tree is 2.

Binary Tree Data Structure

In Python, a binary tree is usually implemented using nodes. Each node in the binary tree contains a value, and pointers to its left and right children, if they exist.

Here is a simple class definition for a binary tree node in Python:

class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

Approach 1: Recursive Depth-First Search (DFS)

One of the most intuitive ways to solve this problem is by using a depth-first search. We can recursively traverse the tree, and for each node, compute the minimum depth of its left and right subtrees.

Let’s look at the Python code for this approach:

class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def minDepth(root):
    if not root:
        return 0
    
    left_depth = minDepth(root.left)
    right_depth = minDepth(root.right)
    
    # If a node has only one child, we must take the depth of the side with the child.
    if not root.left or not root.right:
        return 1 + left_depth + right_depth
    
    return 1 + min(left_depth, right_depth)

This approach has a time complexity of O(N), where N is the number of nodes in the tree, since we visit each node once.

Approach 2: Iterative Breadth-First Search (BFS)

Depth-first search can be inefficient if the tree is highly imbalanced. In such cases, breadth-first search can be more efficient. With BFS, we traverse the tree level by level, and the moment we encounter a leaf node, we know that we have found the minimum depth.

Here is Python code that uses BFS to solve the problem:

from collections import deque

class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def minDepth(root):
    if not root:
        return 0
    
    queue = deque([(root, 1)])
    
    while queue:
        node, depth = queue.popleft()
        
        # If this is a leaf node, return the depth.
        if not node.left and not node.right:
            return depth
        
        if node.left:
            queue.append((node.left, depth + 1))
        if node.right:
            queue.append((node.right, depth + 1))

This approach also has a time complexity of O(N), but in cases of highly imbalanced trees, it might find the minimum depth quicker than DFS.

Analyzing Practical Considerations

When solving problems like this, especially in an interview setting, it’s important to consider the practical implications. For example, understanding the trade-offs between DFS and BFS in terms of memory consumption and speed for different shapes of input trees.

Tips and Tricks

  1. Understand the properties of binary trees.
  2. Become familiar with different tree traversal algorithms.
  3. Practice solving tree-based problems regularly.

Conclusion

The Minimum Depth of Binary Tree problem is a classic example of problems that involve binary tree traversal. We discussed both the depth-first and breadth-first approaches to solving this problem, both of which have their own strengths and weaknesses depending on the nature of the input tree. It’s important to understand the fundamentals of binary tree traversals and to practice solving a variety of problems to become proficient in handling tree-based problems.

Leave a Reply