Poseidon's Decision 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, Boolean Expression, 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 does each node in the binary tree represent?
  • Leaf nodes represent boolean values (True or False), and non-leaf nodes represent boolean operators (AND or OR).
• How should the function evaluate the tree?
  • The function should recursively evaluate the tree by applying the boolean operators to the values of the child nodes.
• How should the function behave if the tree is empty?
  • This scenario should not occur based on the problem description, as the tree always contains a boolean expression.

HAPPY CASE
Input: Binary tree representing the expression: (True OR False) AND (True AND False)
Output: False
Explanation: 
- Left Subtree Evaluation: True OR False evaluates to True
- Right Subtree Evaluation: True AND False evaluates to False
- Root Evaluation: True AND False evaluates to False

EDGE CASE
Input: Binary tree representing a single leaf node with value True
Output: True
Explanation: The tree has only one node, so the result is True.

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

• Binary Tree Traversal: Traverse the tree to evaluate the boolean expression.
• Recursion: Use recursion to evaluate the expression based on the structure of the tree.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Recursively evaluate the tree by applying the boolean operators at each non-leaf node to the results of its children.

1) If the current node is a leaf node (no children), return its boolean value.
2) Recursively evaluate the left and right subtrees.
3) If the current node's value is "AND", return the logical AND of the left and right subtree evaluations.
4) If the current node's value is "OR", return the logical OR of the left and right subtree evaluations.

⚠️ Common Mistakes

• Not correctly handling the base case where the node is a leaf.
• Misapplying the boolean operators 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 get_decision(node):
    # Base case: If the node has no children, return its value
    if node.left is None and node.right is None:
        return node.val
    
    # Recursive case: Evaluate the left and right subtrees
    left_eval = get_decision(node.left)
    right_eval = get_decision(node.right)
    
    # Apply the operation at the current node
    if node.val == "AND":
        return left_eval and right_eval
    elif node.val == "OR":
        return left_eval or right_eval

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 examples given:

  - Input 1: Binary tree representing the expression: (True OR False) AND (True AND False)
  - Expected Output: False
  

  - Input 2: Binary tree representing a single leaf node with value True
  - Expected Output: True
  

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.
• Space Complexity: O(H) where H is the height of the tree, due to the recursive call stack.