Binary Tree Min

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

Problem Highlights

• 💡 Difficulty: Easy
• ⏰ Time to complete: 10 mins
• 🛠️ Topics: Trees, Binary Trees, Minimum Value Search

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?

• Question: What should be returned if the tree is empty?
  • Answer: Return None, as there is no minimum value in an empty tree.

HAPPY CASE
Input: TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(6))
Output: 1
Explanation: The minimum value in the tree is 1.

EDGE CASE
Input: None
Output: None
Explanation: No values exist in an empty tree.

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.

This problem is a fundamental tree traversal challenge where the goal is to find the minimum value. It’s a common operation used in scenarios involving optimizations, comparisons, or condition checks within tree-based data structures.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Traverse the tree using a recursive depth-first search to find the lowest value.

1) If the input tree is empty (`node` is None), return None.
2) Otherwise, recurse with a helper that returns `float('inf')` for a null child so missing subtrees do not influence the minimum.
3) At each non-null node, return the minimum of the current node’s value and the recursive minimums of the left and right subtrees.

⚠️ Common Mistakes

• Returning None instead of a numeric maximum when a node is null, which could complicate comparison logic.

4: I-mplement

Implement the code to solve the algorithm.

def tree_min(node):
    """
    Returns the least value in the binary tree rooted at `node`.
    If the tree is empty, return None.
    """
    if node is None:
        return None

    # Helper uses float('inf') as a sentinel so missing children do not affect the min
    def _min(n):
        if n is None:
            return float('inf')
        return min(n.val, _min(n.left), _min(n.right))

    return _min(node)

5: R-eview

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

• Test the function with trees of varying sizes and shapes, including extremely unbalanced trees, to confirm accurate minimum value identification.

6: E-valuate

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

• Time Complexity: O(n) where n is the number of nodes in the tree, as each node’s value needs to be checked.
• Space Complexity: O(h) where h is the height of the tree due to the recursion stack, potentially reaching O(n) in a highly skewed tree.