NUHMAN.com

Introduction

LeetCode 111: Minimum Depth of Binary Tree asks us to determine the minimum depth of a binary tree. The minimum depth is defined as the number of nodes along the shortest path from the root node down to the nearest leaf node. A leaf node is a node with no children.

This problem can be approached using two main methods: Breadth-First Search (BFS) or Depth-First Search (DFS). Both methods are effective, but the BFS approach is typically preferred for problems involving minimum depth since it explores nodes level by level, guaranteeing the shortest path to a leaf node.

Problem Statement

Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node to the nearest leaf node.

Example:

go

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

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

Approach:

Using Breadth-First Search (BFS)

The Breadth-First Search (BFS) approach is well-suited for this problem because BFS explores nodes level by level. As soon as we encounter a leaf node, we can immediately return the current depth, ensuring that we find the shortest path.

1. BFS Algorithm:

• We use a queue to store nodes along with their depths.
• Start from the root node and process each level.
• If we find a leaf node (a node with no children), return the current depth.

1. DFS Algorithm (Alternative Approach):

• Alternatively, we can use Depth-First Search (DFS) to explore the tree.
• For each node, we calculate the depth of its left and right subtrees.
• The minimum depth at each node is the smaller of the two subtrees’ depths plus one.
• A leaf node (no children) has a depth of 1.

Go Implementation

Solution Using BFS

go

package main

import "container/list"

// TreeNode represents a node in the binary tree.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// minDepth uses BFS to find the minimum depth of the binary tree.
func minDepth(root *TreeNode) int {
    // If the tree is empty, return 0.
    if root == nil {
        return 0
    }

    // Use a queue to implement BFS.
    queue := list.New()
    queue.PushBack(&Node{root, 1})

    // Perform BFS.
    for queue.Len() > 0 {
        front := queue.Front()
        queue.Remove(front)
        current := front.Value.(*Node)

        // If the current node is a leaf node, return its depth.
        if current.node.Left == nil && current.node.Right == nil {
            return current.depth
        }

        // Add left and right children to the queue with incremented depth.
        if current.node.Left != nil {
            queue.PushBack(&Node{current.node.Left, current.depth + 1})
        }
        if current.node.Right != nil {
            queue.PushBack(&Node{current.node.Right, current.depth + 1})
        }
    }

    return 0
}

// Node is a helper structure used to store the node and its depth in the BFS queue.
type Node struct {
    node  *TreeNode
    depth int
}

Explanation:

1. TreeNode Structure:

• The TreeNode struct represents a node in the binary tree with an integer value (Val), and pointers to its left and right children (Left and Right).

1. minDepth Function (BFS Approach):

• This function finds the minimum depth of a binary tree using BFS.
• A queue is used to perform the BFS, and we store each node along with its current depth in the queue.
• Starting with the root node, we explore all nodes level by level.
• When we encounter a leaf node (a node without children), we return its depth as the result.
• As soon as we find the first leaf node, we can safely return the minimum depth because BFS guarantees that we encounter the leaf node at the shallowest level.

1. Node Helper Structure:

• The Node structure is a helper type used to store a binary tree node along with its depth during the BFS traversal.

Alternative Solution Using DFS

Solution Using DFS

go

// minDepth uses DFS to find the minimum depth of the binary tree.
func minDepthDFS(root *TreeNode) int {
    // If the tree is empty, return 0.
    if root == nil {
        return 0
    }

    // If the node has no children, return 1 (leaf node).
    if root.Left == nil && root.Right == nil {
        return 1
    }

    // If only the left child exists, calculate the depth recursively.
    if root.Left == nil {
        return minDepthDFS(root.Right) + 1
    }

    // If only the right child exists, calculate the depth recursively.
    if root.Right == nil {
        return minDepthDFS(root.Left) + 1
    }

    // If both children exist, calculate the minimum depth from both subtrees.
    leftDepth := minDepthDFS(root.Left)
    rightDepth := minDepthDFS(root.Right)

    return min(leftDepth, rightDepth) + 1
}

// min returns the minimum of two integers.
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

Explanation:

1. DFS Approach:

• In this approach, we use DFS to explore the tree.
• Starting from the root, we recursively calculate the minimum depth of the left and right subtrees.
• If a node has no children (leaf node), its depth is considered as 1.
• If both left and right subtrees exist, we calculate the depth for both and return the minimum of the two, incremented by 1 to account for the current node.
• This continues until we find the minimum depth of the entire tree.

1. min Function:

• The min function returns the smaller of two integers. It is used to compute the minimum depth between the left and right subtrees.

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(n)

Where:

• n is the number of nodes in the binary tree.

Time Complexity:

• The time complexity is O(n) because we visit each node once in either BFS or DFS traversal.

Space Complexity:

• The space complexity is O(n), as we may need to store all nodes in the queue (BFS) or recursion stack (DFS) in the worst case, which happens when the tree is unbalanced.

Edge Cases

1. Empty Tree:

• Input: root = nil
• Output: 0
• Explanation: An empty tree has a depth of 0.

1. Single Node Tree:

• Input: root = [1]
• Output: 1
• Explanation: A tree with one node has a depth of 1.

1. Right-Skewed Tree:

• Input: root = [1,null,2,null,3,null,4]
• Output: 4
• Explanation: The tree is right-skewed, and the minimum depth is equal to the number of nodes in the tree.

1. Balanced Tree:

• Input: root = [3,9,20,null,null,15,7]
• Output: 2
• Explanation: The tree is balanced, and the minimum depth is 2 as the leaf nodes are at the second level.

Conclusion

LeetCode 111: Minimum Depth of Binary Tree is a problem that tests your understanding of binary tree traversal. We presented two approaches for solving the problem: Breadth-First Search (BFS), which guarantees finding the shortest path to a leaf node, and Depth-First Search (DFS), which explores the entire tree recursively. Both approaches have O(n) time complexity, where n is the number of nodes in the tree, and O(n) space complexity.