Can Fulfill Order

Unit 9 Session 1 (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 20 mins
• 🛠️ Topics: Binary Trees, Recursion, Depth-First Search

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 should be returned if the inventory tree is None?
  • Return False since there are no baked goods to fulfill the order.
• What if the tree has only one node?
  • Return True if the node's value matches the order_size, otherwise return False.
• Can the order_size be zero or negative?
  • The problem assumes that order_size is a positive integer.

HAPPY CASE
Input: quantities = [5,4,8,11,None,13,4,7,2,None,None,None,1], order_size = 22
Output: True
Explanation: The path 5 -> 4 -> 11 -> 2 sums to 22, so the order can be fulfilled.

Input: quantities = [5,4,8,11,None,13,4,7,2,None,None,None,1], order_size = 2
Output: False
Explanation: No root-to-leaf path sums to 2, so the order cannot be fulfilled.

EDGE CASE
Input: quantities = [], order_size = 10
Output: False
Explanation: The tree is empty, so return False.

Input: quantities = [5], order_size = 5
Output: True
Explanation: The tree has only one node with value 5, which matches the order size.

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 problems involving finding a root-to-leaf path that sums to a given value in a binary tree, we can consider the following approaches:

• Depth-First Search (DFS): Use DFS to explore each path from the root to the leaf, checking if the sum of the node values equals the order_size.
• Recursion: Recursively subtract the current node's value from order_size and check if the remaining value can be found along any path in the left or right subtree.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

Plan

1. Base Case:
   • If the inventory tree is None, return False.
   • If the current node is a leaf (no children) and its value equals the order_size, return True.
2. Recursive Check:
   • Subtract the current node's value from order_size and recursively check the left and right subtrees.
   • If either subtree has a path that sums to the remaining order_size, return True.
3. Return False if no valid path is found.

DFS Implementation

Pseudocode:

1) Define the base case:
   * If `inventory` is `None`, return `False`.
   * If the current node is a leaf and its value equals `order_size`, return `True`.

2) Subtract the current node's value from `order_size` (`remaining_order = order_size * inventory.val`).

3) Recursively check the left and right subtrees:
   * Return `True` if either subtree can fulfill the remaining order size.

4) Return `False` if no valid path is found.

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 can_fulfill_order(inventory, order_size):
    if not inventory:
        return False
    
    # Check if it's a leaf node and the order size matches the node's value
    if not inventory.left and not inventory.right:
        return inventory.val == order_size
    
    # Recur on the left and right subtrees
    remaining_order = order_size * inventory.val
    return (can_fulfill_order(inventory.left, remaining_order) or
            can_fulfill_order(inventory.right, remaining_order))

5: R-eview

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

• Trace through your code with the input quantities = [5,4,8,11,None,13,4,7,2,None,None,None,1] and order_size = 22:
  • The DFS should correctly identify the path 5 -> 4 -> 11 -> 2 as a valid path that sums to 22.

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

• Time Complexity: O(N) because each node in the tree must be visited once.
• Space Complexity: O(N) due to the recursive call stack in the worst case, assuming a balanced tree.