Can Fulfill Order - codepath/compsci_guides GitHub Wiki

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.

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