Leetcode 111: Minimum Depth of Binary Tree

Input: The input is a binary tree represented by its root node.

Example: root = [1,null,2,null,3,null,4]

Constraints:

• The number of nodes in the tree is in the range [0, 10^5].

• -1000 <= Node.val <= 1000

Output: The output is the minimum depth of the binary tree, which is the number of nodes along the shortest path from the root to a leaf node.

Example: 5

Constraints:

• The minimum depth is always a positive integer if the tree is non-empty.

Goal: The goal is to find the minimum depth by recursively checking the depth of the left and right subtrees and choosing the minimum of them.

Steps:

• If the tree is empty, return 0.

• Traverse the tree recursively to find the depths of the left and right subtrees.

• If the left or right subtree is NULL, return the depth of the other subtree.

• Return the minimum of the left and right subtree depths plus one to account for the current node.

Goal: Ensure that the solution handles large inputs efficiently.

Steps:

• The algorithm must handle trees with up to 10^5 nodes.

Assumptions:

• The input is a valid binary tree.

• Input: Input: root = [10,5,15,null,null,12,20]

• Explanation: The tree is balanced and has a minimum depth of 2, as the shortest path from the root to a leaf is from 10 to 15.

• Input: Input: root = [1,null,2,null,3,null,4]

• Explanation: The tree is a straight line, and the minimum depth is 5, which corresponds to the path from 1 to 4.

Approach: To find the minimum depth of the binary tree, we need to recursively traverse the tree and calculate the depth of each subtree, ensuring that we take the shortest path to a leaf node.

Observations:

• A recursive approach can be used where the base case checks for null nodes and returns a depth of 0.

• At each step, we compare the depth of the left and right subtrees and return the smaller value.

• We can optimize by handling cases where one of the subtrees is null separately to avoid unnecessary recursive calls.

Steps:

• Create a helper function to recursively calculate the minimum depth.

• For each node, check if it has a left or right child. If one side is null, return the depth of the other side.

• At each node, return the minimum of the depths of the left and right subtrees plus 1.

Empty Inputs:

• If the input tree is empty, return 0, as there are no nodes in the tree.

Large Inputs:

• The algorithm should efficiently handle large trees, up to the constraint of 10^5 nodes.

Special Values:

• The algorithm should work even for edge cases like a tree with only one node, where the minimum depth is 1.

Constraints:

• The algorithm should run in O(n) time, where n is the number of nodes in the tree, to handle large inputs.

int minDepth(TreeNode* root) {
    
    if(root == NULL) return 0;
    
    int l = minDepth(root->left);
    int r = minDepth(root->right);
    
    if(root->left && root->right) {
        return 1 + ((l < r)? l: r);            
    }
    
    if(root->left) {
        return 1 + l;                        
    }

    return 1 + r;                        
}

1 : Function Declaration

int minDepth(TreeNode* root) {

Define the main function to compute the minimum depth of a binary tree.

2 : Base Case

    if(root == NULL) return 0;

Base case: If the tree is empty, return 0 as the depth.

3 : Recursive Call

    int l = minDepth(root->left);

Recursively calculate the minimum depth of the left subtree.

4 : Recursive Call

    int r = minDepth(root->right);

Recursively calculate the minimum depth of the right subtree.

5 : Condition Evaluation

    if(root->left && root->right) {

Check if both left and right children exist.

6 : Return Statement

        return 1 + ((l < r)? l: r);

Return the minimum depth of the left or right subtree plus 1 for the current node.

7 : Condition Evaluation

    if(root->left) {

Check if only the left child exists.

8 : Return Statement

        return 1 + l;

Return the depth of the left subtree plus 1 for the current node.

9 : Whitespace

Add spacing for better readability.

10 : Return Statement

    return 1 + r;

If only the right child exists, return its depth plus 1 for the current node.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n), where n is the number of nodes, because we visit each node once.

Best Case: O(1)

Worst Case: O(h)

Description: The space complexity is O(h), where h is the height of the tree, due to the recursion stack.

Leetcode 111: Minimum Depth of Binary Tree

Solution to LeetCode 111: Minimum Depth of Binary Tree Problem

Explore →