Unit 8 Session 1 Standard (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: A binary tree with root value of "+" and children 7 and 5
Output: 12
Explanation: The "+" operation is applied to the two children: 7 + 5 = 12.
EDGE CASE
Input: A binary tree with root value of "-" and children 10 and 20
Output: -10
Explanation: The "-" operation is applied to the two children: 10 - 20 = -10.
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 Tree Evaluation problems, we want to consider the following approaches:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Evaluate the yield of the tree by applying the mathematical operation at the root node to its two children.
1) Check the value of the root node.
2) If the value is "+":
a) Return the sum of the left and right children.
3) If the value is "-":
a) Return the difference between the left and right children.
4) If the value is "*":
a) Return the product of the left and right children.
5) If the value is "/":
a) Return the quotient of the left and right children.
⚠️ Common Mistakes
Implement the code to solve the algorithm.
def calculate_yield(root):
if root.val == "+":
return root.left.val + root.right.val
elif root.val == "-":
return root.left.val - root.right.val
elif root.val == "*":
return root.left.val * root.right.val
elif root.val == "/":
return root.left.val / root.right.val
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
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(1)
because we only perform a constant number of operations based on the tree's structure.O(1)
as no additional space is used beyond the input.