➜ ~

Playing Hacks and Stuffs!

---

Project maintained by h4ckyou Hosted on GitHub Pages — Theme by mattgraham

Minimum Depth of Binary Tree

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.

Note: A leaf is a node with no children.

So let’s take a sample binary tree to work on

First we can maybe say let’s take the approach we used for solving the maximum depth which is depth- first search?

Let’s get the traverse of the left subtree

Now the traverse of the right subtree

The minimum value would be our return value?

We can also confirm that’s the right value by getting the minimum between the left and right subtree

From the image above we can see the left subtree has just two nodes while the right has three nodes so the minimum between this two subtress is basically 2

That would work (the script proposed) but not in the case for all binary trees

Let’s say for example this binary tree

We can see that it only has right subtree and we can tell the minimum value is 4 because no comparison against the left subtree

Can you see why the script won’t work?

Well there’s no comparison to check if the node.left == None or node.right == None

So we need to handle a case where there’s no left subtree or right subtree

With that said here’s my solve script is in the link below

Solve Script: link

Leetcode Submission Script

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0

        if root.left is None:
            return 1 + self.minDepth(root.right)
        
        if root.right is None:
            return 1 + self.minDepth(root.left)
        
        left_dept = self.minDepth(root.left)
        right_dept = self.minDepth(root.right)

        return 1 + min(left_dept, right_dept)