Unit 8 Session 1 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:
Tree structure:
+
/ \
- *
/ \ / \
4 2 10 2
Output: 22
Explanation:
- Evaluate the left subtree: 4 - 2 = 2
- Evaluate the right subtree: 10 * 2 = 20
- Combine the results with the root operation: 2 + 20 = 22
EDGE CASE
Input:
Tree structure with only one node:
5
Output: 5
Explanation: The tree has only one node, so the result is 5.
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 Arithmetic Expression Evaluation problems, we want to consider the following approaches:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Traverse the tree recursively, calculating the result of the expression by applying operations at each non-leaf node.
1) If the current node is a leaf node (no children), return its value.
2) Recursively calculate the yield of the left subtree.
3) Recursively calculate the yield of the right subtree.
4) Apply the operation at the current node to the results from the left and right subtrees.
5) Return the result.
⚠️ 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 calculate_yield(root):
if root.left is None and root.right is None:
return root.val
# Recursively calculate the yield of the left and right subtrees
left_yield = calculate_yield(root.left)
right_yield = calculate_yield(root.right)
# Apply the operation at the current node
if root.val == "+":
return left_yield + right_yield
elif root.val == "-":
return left_yield - right_yield
elif root.val == "*":
return left_yield * right_yield
elif root.val == "/":
return left_yield / right_yield
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
+
/ \
- *
/ \ / \
4 2 10 2
Expected Output: 22
5
Expected Output: 5
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
Assume N
represents the number of nodes in the binary tree.
O(N)
because the algorithm needs to visit each node in the tree to evaluate the expression.O(H)
where H
is the height of the tree, due to the recursive call stack.