Minimum Depth of Binary Tree

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end
# @param {TreeNode} root
# @return {Integer}
def min_depth(root)
  if root.nil?
      return 0
  end
  if root.left.nil? && root.right.nil?
      return 1
  end

    minimum_depth = Float::INFINITY

    if root.left
        left = min_depth(root.left)
        minimum_depth = [left, minimum_depth].min
    end
    if root.right
        right = min_depth(root.right)
        minimum_depth = [right, minimum_depth].min
    end

    return 1 + minimum_depth
end

Identifying Problem Isomorphism

“111. Minimum Depth of Binary Tree” is about calculating the minimum depth (or height) of a binary tree from its root to the nearest leaf node.

An isomorphic problem to this is “112. Path Sum”. In the Path Sum problem, the goal is to determine if the tree has a root-to-leaf path such that adding up all the values along the path equals a given target sum.

They both require similar depth-first search traversal techniques to solve. In the Minimum Depth problem, you’re searching for the shortest root-to-leaf path, while in the Path Sum problem, you’re searching for a specific sum along a root-to-leaf path. Thus, both problems involve exploring all possible root-to-leaf paths in the tree. Although the criteria for what constitutes a valid or optimal path differs, the underlying traversal and path exploration methods are similar, making these problems isomorphic at a structural level.

10 Prerequisite LeetCode Problems

“111. Minimum Depth of Binary Tree” is a classic binary tree traversal problem. Here are 10 problems to understand the basics of tree traversal:

  1. 104. Maximum Depth of Binary Tree: It’s a straightforward application of tree traversal and can be solved with both DFS and BFS methods.

  2. 102. Binary Tree Level Order Traversal: This problem is a simple BFS problem on trees, which helps understand the concept of levels in a tree.

  3. 101. Symmetric Tree: This problem can be solved with both BFS and DFS, and introduces the concept of symmetric binary trees.

  4. 107. Binary Tree Level Order Traversal II: This problem is a variant of the level order traversal where you return the result in reverse order.

  5. 226. Invert Binary Tree: It’s a simple problem where you swap the left and right subtrees for all nodes in the tree.

  6. 257. Binary Tree Paths: This problem requires a simple DFS to find all root-to-leaf paths in a tree.

  7. 112. Path Sum: This problem introduces the concept of a path sum in a binary tree.

  8. 589. N-ary Tree Preorder Traversal: This problem extends the concept of tree traversal to n-ary trees, helping you prepare for more complex tree problems.

  9. 590. N-ary Tree Postorder Traversal: This is another n-ary tree problem where you have to return the postorder traversal of the tree.

  10. 700. Search in a Binary Search Tree: This problem introduces the concept of Binary Search Tree and how the properties of BST can be utilized for efficient search.

Understand different traversal strategies in a binary tree, the concept of depth, and how to handle recursive function calls in a tree, all of which are crucial for solving problem 111.

The problem we are trying to solve here is to find the very first leaf in the tree and return its depth (no matter left or right leaf).

Question rephrase: Find number of nodes between root node and nearest leaf node from the root node (both included)

You can solve this problem using a breadth-first search (BFS) approach. With BFS, the first time you encounter a leaf node (a node with no children), it will be the one with the minimum depth, because BFS processes nodes level by level starting from the root.

Here is a Python solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from collections import deque

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

        queue = deque([(root, 1)])
        while queue:
            node, depth = queue.popleft()
            if node:
                children = [node.left, node.right]
                if not any(children):
                    return depth
                for child in children:
                    if child:
                        queue.append((child, depth + 1))

The algorithm uses a queue to process nodes level by level. Each time it dequeues a node, it checks if the node is a leaf node. If it is, it immediately returns the depth of that node. Otherwise, it enqueues the children of the node with their depth incremented by one. If the tree is empty, the function returns zero.

Note: The TreeNode class is assumed to be already defined. This class is typically provided in problems involving trees on online judges. The above code is a sample of how you would implement the solution on these platforms. You can replace the TreeNode class with the appropriate class or data type suitable for your specific programming environment.

Recursive Solution

Given the constraints, a recursive solution (which essentially uses a depth-first search approach) can work. However, it’s important to note that in the worst-case scenario (a skewed tree), the recursion could be very deep, which could lead to stack overflow for extremely large inputs. But since the constraints indicate that the number of nodes is in the range [0, 10^5], this should be manageable in most modern systems.

Here is how you could implement the recursive solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution(object):
    def minDepth(self, root):
        if root is None:  return 0

        leftDepth = self.minDepth(root.left)
        rightDepth = self.minDepth(root.right)

        if root.left is None and root.right is None:
            return 1

        if root.left is None:
            return 1 + rightDepth

        if root.right is None:
            return 1 + leftDepth

        return min(leftDepth, rightDepth) + 1;

This solution recursively finds the minimum depth of the left and right subtrees and returns the smaller one plus one (for the current node). If one of the subtrees doesn’t exist, it only calculates the minimum depth of the existing subtree. If the current node is a leaf node, it returns 1. If the root is null, it returns 0.

This solution works and is easy to understand, but it has a higher time complexity than the BFS solution, because it needs to visit every node in the tree. In comparison, the BFS solution stops as soon as it finds a leaf node, so it may not need to visit every node. However, for this problem, both solutions should work fine within the given constraints.

Problem Classification

  1. Binary Trees: The problem revolves around a binary tree data structure. A binary tree is a tree-type non-linear data structure with a maximum of two children for each parent.

  2. Tree Depth: The problem requires understanding of the concept of tree depth, which is the shortest path from the root to a leaf in this context.

  3. Recursion: The problem requires knowledge of recursion, a common strategy used in tree traversal, where a function calls itself to solve smaller instances of the same problem.

  4. Tree Traversal: Understanding different types of tree traversal methods (in-order, pre-order, post-order) is crucial for solving such problems, as different methods can lead to different solutions. This problem involves an exploration that is similar to a depth-first search traversal.

  5. Minimum Path: The problem is specifically asking for the minimum depth of the tree, which involves understanding how to traverse the tree to find and compare all possible paths from root to the leaves.

Language Agnostic Coding Drills

  1. Understanding Binary Trees: This problem involves binary trees. Understanding how they work is the first key step.

  2. Recursive Functions: The solution involves recursion, as it dives deeper into each level of the tree.

  3. Tree Depth: This problem involves determining the minimum depth of a tree, which is the shortest path from the root to a leaf.

Targeted Drills in Python

  1. Understanding Binary Trees:
1
2
3
4
5

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
  1. Recursive Functions:
1
2
3
4
5
6
7

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

print(factorial(5))  # prints 120
  1. Tree Depth:

Here we can introduce the concept of tree depth by implementing a function that calculates the maximum depth. Later, this can be adapted to find the minimum depth:

1
2
3
4
5
6
7
8

class Solution:
    def maxDepth(self, root):
        if root is None: 
            return 0 
        else: 
            left_height = self.maxDepth(root.left) 
            right_height = self.maxDepth(root.right) 
            return max(left_height, right_height) + 1

To adapt this to find the minimum depth, we just need to change the max to min, and add checks for the case where a node only has one child. This would lead us directly to the solution of the original problem.

Q&A

why we can’t regard the root node as a part of left tree or right tree? I think it’s resonable. Could someone help me ?

When we talk about a binary tree, we usually conceptualize it in terms of a root node and its two subtrees: the left subtree and the right subtree. The root node is seen as a separate entity that connects these two subtrees.

This view of the binary tree is useful for recursive algorithms, where we solve a problem on the tree by solving the same problem on the left subtree and the right subtree and combining these solutions in some way.

From another perspective, you could say that the root node is part of both the left and right subtrees, because it is an ancestor of all nodes in both subtrees. But this viewpoint is less useful for most algorithmic problems on binary trees, because it doesn’t allow us to easily divide the tree into smaller parts that we can solve independently.

In the end, whether we regard the root as part of the left subtree, the right subtree, both, or neither depends on what is most useful for the problem we are trying to solve. However, the conventional view is to see the root as a separate entity that connects the left and right subtrees, and this view is the most useful in a majority of cases.

Why [1,2] should return 2 not 1? and [1,null,2] should return 2 not 1? and [1,2,3,4,null,null,5] should return 3 not 2?

The minimum depth of a binary tree is the number of nodes along the shortest path from the root node down to the nearest leaf node. A leaf node is a node with no children.

  1. For the tree [1,2], it looks like:

     1
/

    2

    The shortest path to a leaf node is 1 -> 2, which is of length 2, hence the answer is 2.

  2. For the tree [1,null,2], it looks like:

     1
  \
   2

    The shortest path to a leaf node is 1 -> 2, which is of length 2, hence the answer is 2.

  3. For the tree [1,2,3,4,null,null,5], it looks like:

       1
  / \
 2   3
/     \

    4 5

    The shortest path to a leaf node is 1 -> 3 -> 5, which is of length 3, hence the answer is 3.

Remember, a leaf is a node with no children. So even though the node 2 is closer to the root in the third tree, it’s not a leaf node because it has a child node (4), so the path to it doesn’t count when calculating the minimum depth.

Anyone explain why testcase2 will give 5 as output not 1.

The tree for testcase 2 is represented as [2,null,3,null,4,null,5,null,6], and the actual structure is as follows:

    2
     \
      3
       \
        4
         \
          5
           \
            6

You can see that the shortest path from the root node (2) to the nearest leaf node (which is 6) is of length 5, traversing through nodes 3, 4, 5, and 6.

The rule to calculate the minimum depth is from the root node down to the nearest leaf node. A leaf node is a node with no children. In this case, node 6 is the only leaf node. So the minimum depth of the tree is the distance from root node 2 to leaf node 6, which is 5.

So, the output is 5, not 1.