Calculating Yield II - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

• 💡 Difficulty: Easy
• ⏰ Time to complete: 10 mins
• 🛠️ Topics: Binary Tree, Recursion, Arithmetic Expression Evaluation

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 does each node in the binary tree represent?
  • Leaf nodes represent numeric values, and non-leaf nodes represent arithmetic operators.
• What does the function need to return?
  • The function needs to return the result of evaluating the arithmetic expression represented by the tree.
• How should the function behave if the tree is empty?
  • The problem does not specify an empty tree case, but in general, an empty tree might return 0 or an error depending on the context.

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.

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

• Binary Tree Traversal: Traverse the tree to evaluate the arithmetic expression.
• Recursion: Use recursion to calculate the result of the expression by applying operations at each node.

3: P-lan

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

• Not correctly handling the case where the node is a leaf.
• Misapplying arithmetic operations when evaluating non-leaf nodes.

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

5: R-eview

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

• Input 1: Tree structure:

          +
         / \ 
        -   *
      / \   / \
     4   2 10  2

Expected Output: 22

• Input 2: Tree structure with only one node:

          5

Expected Output: 5

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(N) because the algorithm needs to visit each node in the tree to evaluate the expression.
• Space Complexity: O(H) where H is the height of the tree, due to the recursive call stack.