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