111. Minimum Depth of Binary Tree


Problem Description

In this problem, we are given a binary tree and we are required to determine its minimum depth. The minimum depth is defined as the number of nodes present along the shortest path from the root node to the nearest leaf node. Importantly, a leaf node is characterized as a node that does not have any children.

Intuition

To solve this problem, the idea is to use a depth-first search (DFS) approach to recursively traverse the tree and find the depth of the shortest path from the root to a leaf node. Here are the steps we would follow:

  • Base Cases: First, we check some base cases:

    • If the node we're looking at is None, we return 0 because we're dealing with a non-existent (empty) sub-tree.
    • If the node is a leaf node (both left and right children are None), we would return 1 because the path consists only of the current node.
  • Recursive Steps: If the base cases aren't met, we proceed with the following logic:

    • If only one of the children is None, this means that the path must go through the side that has a child. We recursively calculate the depth of this valid side and add 1 for the current node.
    • If both left and right children are present, we recursively calculate the depth of both sides and choose the smaller one, then add 1 to account for the current node.

By applying this approach, we ensure that we find the shortest path that reaches a leaf node, satisfying the requirement to determine the minimum depth of the tree.

Solution Approach

The implementation of the solution uses a straightforward recursive depth-first search (DFS) technique to traverse the binary tree. The following details outline the steps taken in the algorithm along with the relevant data structures and patterns:

  • A recursive function minDepth is defined which takes a TreeNode as an argument.
  • Base Case Handling: The algorithm first checks if the root node is None and returns 0, indicating an empty tree has a depth of 0.
  • For a non-empty tree, two scenarios are handled separately:
    1. One Child is None: If either root.left or root.right is None, this implies that we do not need to consider that path because it doesn't lead to a leaf. The depth, in this case, is found by recursively calling minDepth on the non-None child and adding 1 for the current node.
    2. Both Children Exist: If both root.left and root.right are not None, the recursion is performed on both and the minimum of the two depths is taken. This minimum depth represents the shortest path to a leaf node because we are interested only in the smallest count of steps to reach a leaf.
  • Combining Recursive Call Results: After considering the appropriate cases, the depth is incremented by 1 to account for the current root node and the result is returned.

No additional data structures are needed; the recursive stack implicitly built from the function calls keeps track of the recursion depth. The DFS pattern is suitable because we need to dive into the depths of the tree branches to find leaf nodes and evaluate their depth.

The Python code for the reference solution ensures that the branching occurs as necessary and handles each node in an efficient and succinct manner.

1class Solution:
2    def minDepth(self, root: Optional[TreeNode]) -> int:
3        if root is None:
4            return 0
5        if root.left is None:
6            return 1 + self.minDepth(root.right)
7        if root.right is None:
8            return 1 + self.minDepth(root.left)
9        return 1 + min(self.minDepth(root.left), self.minDepth(root.right))

This recursive approach is both elegant and effective for the problem at hand.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's illustrate the solution approach with a small example binary tree:

Let's say our binary tree looks like this (numbers represent the node values, not depth):

1     1
2    / \
3   2   3
4  / 
5 4  

We need to find the minimum depth of this tree. We apply the solution approach as follows:

  1. We start with the root node (1). Since it is not None, we move to the recursive steps.
  2. The root node (1) has two children – nodes 2 and 3.
  3. We then apply the DFS approach. We look at the left child first, which is node 2.
  4. Node 2 is not a leaf since it has one child, node 4. Since its right child is None, we find the depth by recursively calling minDepth on its left child (node 4).
  5. Node 4 is a leaf node because it has no children. Hence the base case is met, and we return 1.
  6. Now, since node 2 had its right child as None, according to our recursive formula, we return 1 (depth of node 4) + 1 (node 2 itself), which equals 2.
  7. Now back to the root node (1), we need to consider its right child, which is node 3.
  8. Node 3 is a leaf node with no children. Hence, the base case is met, and we return 1.
  9. Now, we compare the minimum depth between the left and right subtrees of the root. The left subtree has a depth of 2 (from node 2 to node 4), and the right subtree has a depth of 1 (node 3 alone).
  10. We, therefore, choose the smaller depth, which is 1, and add 1 to account for the root. So, the minimum depth of the tree is 1 + 1 = 2, which represents the path [1 -> 3].

Here's how the solution approach effectively finds the minimum depth for this binary tree which is 2, denoting the shortest path from root to the nearest leaf node.

Python Solution

1class TreeNode:
2    """Definition for a binary tree node."""
3
4    def __init__(self, val=0, left=None, right=None):
5        self.val = val
6        self.left = left
7        self.right = right
8
9
10class Solution:
11    def minDepth(self, root: Optional[TreeNode]) -> int:
12        """Calculate the minimum depth of the binary tree.
13      
14        The minimum depth is the number of nodes along the shortest path
15        from the root node down to the nearest leaf node.
16        """
17        # If the root is None, the tree is empty, so return 0.
18        if root is None:
19            return 0
20      
21        # If there is no left child, compute the minDepth of the right subtree 
22        # and add 1 to account for the current node.
23        if root.left is None:
24            return 1 + self.minDepth(root.right)
25      
26        # If there is no right child, compute the minDepth of the left subtree 
27        # and add 1 to account for the current node.
28        if root.right is None:
29            return 1 + self.minDepth(root.left)
30      
31        # If the tree has both left and right children, compute the minDepth 
32        # of both subtrees, take the minimum, and add 1 for the current node.
33        return 1 + min(self.minDepth(root.left), self.minDepth(root.right))
34

Java Solution

1/**
2 * Definition for a binary tree node.
3 */
4class TreeNode {
5    int val;
6    TreeNode left;
7    TreeNode right;
8
9    TreeNode() {}
10
11    TreeNode(int val) {
12        this.val = val;
13    }
14
15    TreeNode(int val, TreeNode left, TreeNode right) {
16        this.val = val;
17        this.left = left;
18        this.right = right;
19    }
20}
21
22/**
23 * This class contains a method to calculate the minimum depth of a binary tree.
24 */
25class Solution {
26  
27    /**
28     * Finds the minimum depth of a binary tree recursively.
29     * The minimum depth is the number of nodes along the shortest path from 
30     * the root node down to the nearest leaf node.
31     * 
32     * @param root The root node of the binary tree.
33     * @return The minimum depth of the tree.
34     */
35    public int minDepth(TreeNode root) {
36        // If root is null, then there is no tree, and the depth is 0.
37        if (root == null) {
38            return 0;
39        }
40      
41        // If the left child is null, recursively find the minDepth of the right subtree.
42        // Here the right subtree's minDepth is used because without the left child,
43        // the path through the right child is the only path to a leaf node.
44        if (root.left == null) {
45            return 1 + minDepth(root.right);
46        }
47      
48        // If the right child is null, recursively find the minDepth of the left subtree.
49        // Analogous to the previous condition, the left subtree's minDepth is used here.
50        if (root.right == null) {
51            return 1 + minDepth(root.left);
52        }
53      
54        // If neither child is null, find the minDepth of both subtrees and
55        // take the minimum of the two, adding 1 for the current node.
56        return 1 + Math.min(minDepth(root.left), minDepth(root.right));
57    }
58}
59

C++ Solution

1#include <algorithm> // To use the std::min function
2
3/**
4* Definition for a binary tree node.
5*/
6struct TreeNode {
7    int value; // Renamed 'val' to 'value' for clarity
8    TreeNode *left;
9    TreeNode *right;
10    // Constructor initializes the node with a value and optional left and right children
11    TreeNode(int val, TreeNode *leftChild = nullptr, TreeNode *rightChild = nullptr) 
12        : value(val), left(leftChild), right(rightChild) {}
13};
14
15class Solution {
16public:
17    // Function to find the minimum depth of a binary tree
18    int minDepth(TreeNode* root) {
19        // Base case: if tree is empty, return depth of 0
20        if (!root) {
21            return 0;
22        }
23      
24        // If left child does not exist, recurse on right subtree and add 1 to the depth
25        if (!root->left) {
26            return 1 + minDepth(root->right);
27        }
28      
29        // If right child does not exist, recurse on left subtree and add 1 to the depth
30        if (!root->right) {
31            return 1 + minDepth(root->left);
32        }
33      
34        // If both left and right children exist, find the minimum of the two depths and add 1
35        return 1 + std::min(minDepth(root->left), minDepth(root->right));
36    }
37};
38

Typescript Solution

1// Definition for a binary tree node.
2interface TreeNode {
3    val: number;
4    left: TreeNode | null;
5    right: TreeNode | null;
6}
7
8/**
9 * Calculate the minimum depth of a binary tree.
10 * The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
11 * 
12 * @param {TreeNode | null} root - The root node of the binary tree.
13 * @return {number} - The minimum depth of the tree.
14 */
15function minDepth(root: TreeNode | null): number {
16    // Base case: if the tree is empty, return 0
17    if (root === null) {
18        return 0;
19    }
20  
21    // Get the left and right child nodes
22    const leftChild = root.left;
23    const rightChild = root.right;
24  
25    // If the left child is null, recursively calculate the minimum depth of the right subtree and add 1 for the current node
26    if (leftChild === null) {
27        return 1 + minDepth(rightChild);
28    }
29  
30    // If the right child is null, recursively calculate the minimum depth of the left subtree and add 1 for the current node
31    if (rightChild === null) {
32        return 1 + minDepth(leftChild);
33    }
34  
35    // If both child nodes are present, calculate the minimum depth of both subtrees, take the lesser value, and add 1 for the current node
36    return 1 + Math.min(minDepth(leftChild), minDepth(rightChild));
37}
38

Time and Space Complexity

The given code is a recursive solution 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.

Time Complexity

The time complexity of the function depends on the structure of the tree. In the worst case, the tree is completely unbalanced, i.e., every node has only one child. This leads to a recursive call at each level, resulting in O(n) time complexity, where n is the number of nodes in the tree, as each node is visited once.

In the best case, the tree is completely balanced, and the number of nodes in the tree is 1 for the first level, 2 for the second level, 4 for the third, and so on, until l levels. The total number of nodes n in a balanced binary tree is n = 2^l - 1. The function calls are akin to a binary search in this scenario, the time complexity is O(log n) for a balanced binary tree.

Overall, the average and worst-case time complexities can be considered O(n), since you cannot guarantee the tree is balanced.

Space Complexity

The space complexity is mainly determined by the recursive call stack. In the worst case, where the tree is completely unbalanced (every node has only one child), there would be n recursive calls, resulting in O(n) space complexity.

In the best case, where the tree is balanced, the height of the tree is log n (where n is the number of nodes). This would result in a space complexity of O(log n) due to the height of the recursive call stack.

Thus, the space complexity of the function varies from O(log n) for a balanced binary tree to O(n) for an unbalanced binary tree where n is the number of nodes.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫