Minimum Ocean Depth - codepath/compsci_guides GitHub Wiki

Unit 8 Session 2 Advanced (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 20-25 mins
  • 🛠️ Topics: Trees, Recursion, Depth Calculation

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • What is the structure of the tree?
    • The tree is a binary tree where each node represents a part of the ocean.
  • What operation needs to be performed?
    • The function needs to find the minimum depth of the tree, which is the shortest path from the root to the nearest leaf node.
  • What should be returned?
    • The function should return the minimum depth as an integer.
HAPPY CASE
Input: 
    ocean = TreeNode("Shipwreck", TreeNode("Shallows"), TreeNode("Reef", TreeNode("Cave"), TreeNode("Trench")))
Output: 
    2
Explanation: 
    The shortest path from the root "Shipwreck" to the nearest leaf node is 2 nodes (through "Shallows").

EDGE CASE
Input: 
    ocean = TreeNode("Shipwreck")
Output: 
    1
Explanation: 
    The tree consists of only the root node, so the minimum depth is 1.

2: M-atch

Match what this problem looks like to known categories of problems, e.g., Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Binary Tree problems, we want to consider the following approaches:

  • Recursion: A recursive approach is natural here, as each node's depth can be determined by the depths of its subtrees.
  • Breadth-First Search (BFS): BFS is useful for finding the shortest path in an unweighted tree.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Recursively calculate the minimum depth of the left and right subtrees, and return the smaller of the two depths plus one. Special cases must be handled where a node has only one child, in which case the depth of the non-missing child should be considered.

1) If the current node (`root`) is `None`, return 0 as the depth.
2) If the current node has no left child, return the depth of the right subtree plus 1.
3) If the current node has no right child, return the depth of the left subtree plus 1.
4) If both children are present, return the minimum of the depths of the left and right subtrees plus 1.

⚠️ Common Mistakes

  • Not correctly handling cases where the tree is skewed or where nodes have only one child.
  • Misinterpreting the minimum depth by ignoring the need to account for both subtrees.

4: I-mplement

Implement the code to solve the algorithm.

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.val = value
        self.left = left
        self.right = right

def find_min_depth(root):
    if not root:
        return 0
    
    # If one of the children is missing, we must consider the non-missing child's depth
    if not root.left:
        return find_min_depth(root.right) + 1
    if not root.right:
        return find_min_depth(root.left) + 1
    
    # If both children are present, take the minimum depth of both subtrees
    return min(find_min_depth(root.left), find_min_depth(root.right)) + 1

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

- Example 1:
    - Input: 
        `ocean = TreeNode("Shipwreck", TreeNode("Shallows"), TreeNode("Reef", TreeNode("Cave"), TreeNode("Trench")))`
    - Execution: 
        - Start at root "Shipwreck".
        - "Shipwreck" has two children: "Shallows" and "Reef".
        - "Shallows" has no children, so its depth is 1.
        - "Reef" has two children, so the minimum depth is calculated between "Cave" and "Trench".
        - The minimum depth is 2.
    - Output: 
        2

- Example 2:
    - Input: 
        `ocean = TreeNode("Shipwreck")`
    - Execution: 
        - The tree consists of only the root node, so the minimum depth is 1.
    - Output: 
        1

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Time Complexity:

  • Time Complexity: O(N) where N is the number of nodes in the tree.
    • Explanation: We visit each node exactly once during the traversal to determine the minimum depth.

Space Complexity:

  • Space Complexity: O(H) where H is the height of the tree.
    • Explanation: The recursion stack will use space proportional to the height H of the tree. In a balanced tree, H is O(log N), but in the worst case (skewed tree), it could be O(N).