Leetcode 111. Minimum Depth of Binary Tree (Python)

Related Topic

Depth-First-Search. Tree.

Description

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.

Sample I/O

Example 1

Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its minimum depth = 2.

Methodology

This question can be solved by Depth First Search.

This is a easy level question and it took me long time. To find the maxmium depth of the tree is fairly easy. However to find the minimum depth of a tree is not. There is a tricky thing here that took me long time to figure out.

If a root has left subtree and right subtree, all we need to do is find which subtree has minimum depth min(left_subtree, right_subtree)+1 (for root itself). However if the root has only one subtree either left or right min(left_subtree, right_subtree) will give us 0 + 1 for(root itself), this is incorrect. Root itself can not be leaf node if it has at least one subtree. So if root has only 1 subtree, we are going to get max(leftsubtree, right_subtree)+1.

Code(DFS)

def minDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0
        if root.left and root.right:
            return min(self.minDepth(root.left), self.minDepth(root.right)) + 1
        else:
            return max(self.minDepth(root.left), self.minDepth(root.right)) + 1

BigO

We traversal all nodes of the tree once so time complexity is O(n)