Distributing Sunken Treasure - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

  • 💡 Difficulty: Hard
  • ⏰ Time to complete: 30-40 mins
  • 🛠️ Topics: Trees, Postorder Traversal, Greedy Algorithms

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 friend, and the value of each node represents the number of coins that friend has.
  • What operation needs to be performed?
    • The function needs to distribute the coins such that each node ends up with exactly one coin, using the minimum number of moves.
  • What should be returned?
    • The function should return the minimum number of moves required.
HAPPY CASE
Input: 
    root1 = TreeNode(3, TreeNode(0), TreeNode(0))
Output: 
    2
Explanation: 
    Two moves are required: move one coin from the root to each child.

EDGE CASE
Input: 
    root2 = TreeNode(0, TreeNode(3), TreeNode(0))
Output: 
    3
Explanation: 
    Three moves are required: move two coins from the left child to the root, and then one coin from the root to the right child.

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:

  • Postorder Traversal: A postorder traversal (left-right-root) is a good fit because we need to calculate the excess or deficit of coins at each node starting from the leaves and moving upwards.
  • Greedy Algorithms: The solution involves making local decisions at each node (how to distribute the excess coins) that lead to an optimal global solution.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Perform a postorder traversal of the tree to calculate the number of excess or deficit coins at each node. The number of moves required at each node is the sum of the absolute values of the excess or deficit in its left and right subtrees. The total number of moves is the sum of moves required at all nodes.

1) Define a helper function `postorder(node)` that:
    - If the node is `None`, return 0.
    - Recursively calculate the excess coins in the left subtree (`left_excess`).
    - Recursively calculate the excess coins in the right subtree (`right_excess`).
    - Add the absolute values of `left_excess` and `right_excess` to the total number of moves.
    - Return the total excess coins for the current node, calculated as `node.val - 1 + left_excess + right_excess`.
  
2) In the main `distribute_coins` function:
    - Initialize a list `moves` with one element set to 0 to keep track of the total number of moves.
    - Call the `postorder` function starting from the root.
    - Return the total number of moves.

⚠️ Common Mistakes

  • Forgetting to account for the fact that the node itself needs to end up with exactly one coin.
  • Incorrectly calculating the excess coins, leading to an incorrect number of moves.

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 distribute_coins(root):
    def postorder(node):
        if not node:
            return 0
        
        # Recursively calculate excess coins in the left and right subtrees
        left_excess = postorder(node.left)
        right_excess = postorder(node.right)
        
        # Total moves are the sum of absolute values of excess in the subtrees
        moves[0] += abs(left_excess) + abs(right_excess)
        
        # Return the total excess coins for this node (including its subtrees)
        return node.val - 1 + left_excess + right_excess
    
    moves = [0]  # Using a list to keep a mutable reference to the move count
    postorder(root)
    return moves[0]
    
# Example Usage:
root1 = TreeNode(3, TreeNode(0), TreeNode(0))
root2 = TreeNode(0, TreeNode(3), TreeNode(0))

print(distribute_coins(root1))  # 2
print(distribute_coins(root2))  # 3

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: 
        `root1 = TreeNode(3, TreeNode(0), TreeNode(0))`
    - Execution: 
        - Start at the left child (0 coins): no moves needed, excess is -1.
        - Move to the right child (0 coins): no moves needed, excess is -1.
        - At the root (3 coins): 2 moves needed to balance the excess of -2 from the children.
    - Output: 
        2

- Example 2:
    - Input: 
        `root2 = TreeNode(0, TreeNode(3), TreeNode(0))`
    - Execution: 
        - Start at the left child (3 coins): 2 moves needed to balance the excess of 2.
        - Move to the right child (0 coins): no moves needed, excess is -1.
        - At the root (0 coins): 1 move needed to balance the excess of -1 from the children.
    - Output: 
        3

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 postorder traversal to calculate the total number of moves.

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).