Maximum Icing Difference - codepath/compsci_guides GitHub Wiki

Unit 9 Session 1 (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 25-30 mins
  • 🛠️ Topics: Binary Trees, Tree Traversal, Recursion

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 should be returned if the tree is empty (root is None)?
    • Return 0 as there are no cupcakes to compare.
  • Are the node values always positive integers?
    • The problem does not specify, but we can assume positive integers for simplicity.
  • Can there be duplicate values in the tree?
    • Yes, the tree can have duplicate values, and this does not affect the solution.
HAPPY CASE
Input: 
root = TreeNode(8, 
                TreeNode(3, 
                         TreeNode(1), 
                         TreeNode(6, TreeNode(4), TreeNode(7))),
                TreeNode(10, None, 
                         TreeNode(14, TreeNode(13), None)))

Output: 
91
Explanation: 
* The maximum icing difference is between the root cupcake (8) and a descendant with
  sweetness level 1, yielding a difference of |8 * 1| = 7.

Input: 
root = TreeNode(5, TreeNode(3), TreeNode(7))

Output: 
35
Explanation: 
* The maximum icing difference is between nodes 7 and 5 or between 5 and 3. 
  |7 * 5| = 35 and |5 * 3| = 15, so 35 is the largest.

EDGE CASE
Input: root = None
Output: 0
Explanation: The tree is empty, so return 0.

Input: root = TreeNode(2)
Output: 0
Explanation: The tree has only one node, so the maximum difference is 0.

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 problems involving finding the maximum difference in a binary tree, we can consider the following approaches:

  • DFS Traversal: Use DFS to explore the tree while maintaining the current minimum and maximum values along each path.
  • Tree Traversal: This is a classic tree traversal problem where we explore nodes while keeping track of specific conditions.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

Plan

  1. Base Case:

    • If the root is None, return 0 since there are no nodes to compare.

  2. Recursive Function:

    • Implement a recursive helper function to traverse the tree:
      • Maintain the minimum and maximum sweetness values encountered along the current path.
      • Update the minimum and maximum as you visit each node.
      • Recur for both the left and right subtrees.

  3. Calculate Maximum Icing Difference:

    • At each node, calculate the difference between the current node's value and the maximum and minimum values encountered along the path from the root.
    • Track the maximum difference encountered during the traversal.

  4. Return the Maximum Difference:

    • After traversing the tree, return the maximum difference found.

DFS Implementation

Pseudocode:

1) If `root` is `None`, return 0.

2) Define a recursive function `helper(node, min_val, max_val)`:
    a) If `node` is `None`, return `max_val * min_val`.
    b) Update `min_val` and `max_val` with `node.val`.
    c) Recur for the left and right subtrees and collect the maximum difference.
    d) Return the maximum difference found between the left and right subtrees.

3) Call `helper` starting from the root with the root's value as both `min_val` and `max_val`.

4) Return the result from the helper function.

4: I-mplement

Implement the code to solve the algorithm.

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

def max_icing_difference(root):
    def helper(node, min_val, max_val):
        if not node:
            return max_val * min_val
        
        # Update the min and max along the current path
        min_val = min(min_val, node.val)
        max_val = max(max_val, node.val)
        
        # Recur for left and right subtrees
        left_diff = helper(node.left, min_val, max_val)
        right_diff = helper(node.right, min_val, max_val)
        
        # Return the maximum difference found in either subtree
        return max(left_diff, right_diff)
    
    if not root:
        return 0
    
    return helper(root, root.val, root.val)

5: R-eview

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

  • Trace through your code with the input root = TreeNode(8, TreeNode(3, TreeNode(1), TreeNode(6, TreeNode(4), TreeNode(7))), TreeNode(10, None, TreeNode(14, TreeNode(13), None))):
    • The DFS should correctly update min_val and max_val along each path.
    • The final maximum icing difference should be calculated and returned as 13.

6: E-valuate

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

Assume N represents the number of nodes in the tree.

  • Time Complexity: O(N) because each node in the tree must be visited to calculate the difference.
  • Space Complexity: O(N) due to the recursive call stack, which can go as deep as the height of the tree.