Calculating Yield - codepath/compsci_guides GitHub Wiki

Unit 8 Session 1 Standard (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Easy
• ⏰ Time to complete: 10 mins
• 🛠️ Topics: Binary Tree, 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 are the possible values of the root node?
  • The root node can be one of the following strings: "+", "-", "*", or "/".
• What do the leaf nodes represent?
  • The leaf nodes represent integer values.

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.

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 Tree Evaluation problems, we want to consider the following approaches:

• Binary Tree Traversal: Traverse the tree to evaluate the operation at the root.
• Recursion: Use recursion to solve the problem by evaluating the root based on its children.

3: P-lan

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

• Using the wrong operation for the root node's value.
• Forgetting to handle division by zero (although not explicitly mentioned, it’s good practice to consider).

4: I-mplement

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

5: R-eview

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

• Test with the example given:
  • Input: Tree with root "+" and children 7 and 5
  • Expected Output: 12
  • Verify that the output is correct.

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 binary tree.

• Time Complexity: O(1) because we only perform a constant number of operations based on the tree's structure.
• Space Complexity: O(1) as no additional space is used beyond the input.