Minimum Depth Of Binary Tree - Leetcode Solution

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 down to the nearest leaf node.

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

Explanation: The shortest path is 3->9->20 which has a length of 2.

Solution:

The approach we can take is a recursive approach. We can traverse the binary tree in a depth-first order and keep track of the depth. When we find a leaf node, we return the depth. We then find the minimum of the minimum depths of the left and right subtrees.

Algorithm:

1. If the root is null, return 0
2. If both left and right children are null, return 1
3. If the left child is null, recursively calculate the minimum depth of the right subtree and add 1 to it.
4. If the right child is null, recursively calculate the minimum depth of the left subtree and add 1 to it.
5. If both children are not null, recursively calculate the minimum depth of both the left and right subtrees, and return the minimum of the two plus 1.

Time Complexity:

The time complexity of this algorithm is O(n), where n is the number of nodes in the binary tree. This is because we visit each node exactly once.

Space Complexity:

The space complexity of this algorithm is O(h), where h is the height of the binary tree. This is because there will be h recursive calls on the call stack at the maximum. In the worst case, the binary tree can be skewed, so the height can be equal to n, resulting in a space complexity of O(n).

Implementation:

Here is the implementation of the above approach in Python:

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        if not root.left and not root.right:
            return 1
        if not root.left:
            return self.minDepth(root.right) + 1
        if not root.right:
            return self.minDepth(root.left) + 1
        return min(self.minDepth(root.left), self.minDepth(root.right)) + 1

Here is the implementation of the above approach in Java:

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        if (root.left == null) {
            return minDepth(root.right) + 1;
        }
        if (root.right == null) {
            return minDepth(root.left) + 1;
        }
        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
    }
}

We can see that the implementation in Java is very similar to the implementation in Python.

1