Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

Question

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: {}
Output: 0

Input:  {1,#,2,3}
Output: 3	
Explanation:
	1
	 \ 
	  2
	 /
	3    
it will be serialized {1,#,2,3}

Input:  {1,2,3,#,#,4,5}
Output: 2	
Explanation: 
      1
     / \ 
    2   3
       / \
      4   5  
it will be serialized {1,2,3,#,#,4,5}

Analyzation

Recursion

• Idea This question is solved with DFS (depth first search).

• Algorithm This question is very similar to the 97. Maximum Depth Question of Binary Trees, but requires one more thought. We know that when finding the maximum depth, the recursive condition is: the depth of each node is equal to the maximum depth value of its left and right subtrees plus 1. When finding the minimum depth, if the analogy is to make the depth of each node equal to the minimum depth value of its left and right subtrees plus 1, it is wrong to do so. Take tree = {1,2,#,3} as an example. This is a three-level tree. The minimum depth should be 3, but if the right subtree of node 1 is empty according to the above method, we will get node 1 The conclusion that the minimum depth is 1 does not match the answer. The correct approach is to determine whether there are empty subtrees in the left and right subtrees. If there are, the minimum depth is equal to the depth of the other subtree plus 1.

• Recursive Design Recursive case: For the current node root, we find the depth of the left and right subtrees respectively. If there is an empty subtree, return the depth of the two subtrees plus 1; if there is no empty subtree, return the smaller value of the two depths plus 1. T ermination condition (base case): When the current node is empty, the tree depth is considered to be 0.

The Code

class Solution:
    """
    @param root: The root of binary tree
    @return: An integer
    """
    def minDepth(self, root):
        # write your code here
        if root is None:
            return 0
        if root.left is None:
            return self.minDepth(root.right) + 1
        if root.right is None:
            return self.minDepth(root.left) + 1
            
        return min(self.minDepth(root.left), self.minDepth(root.right)) + 1

Time & Space Complexity

• Time complexity: O(n), where n is the number of nodes. We only visit each node once, so the time complexity is O(n).
• Space complexity: Consider the recursive use of call stack (call stack). Worst case: The tree is completely unbalanced. For example, each node has only the left node. At this time, it will recurse n times, and the storage of the call stack needs to be kept as O(n) Best case: The tree is perfectly balanced. That is, the height of the tree is log(n), and the space complexity is O(log(n))