Unit 8 Session 2 Advanced (Click for link to problem statements)
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?
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.
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:
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
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
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
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
O(N)
where N
is the number of nodes in the tree.
O(H)
where H
is the height of the tree.
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)
.