Pruning Pothos - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

  • 💡 Difficulty: Hard
  • ⏰ Time to complete: 30-35 mins
  • 🛠️ Topics: Trees, Recursion, Tree Pruning

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 is the structure of the tree?
    • The tree is a binary tree where each node represents a segment of a Pothos plant.
  • What operation needs to be performed?
    • The function needs to prune the tree by deleting all leaf nodes with the value target. The pruning should continue until no more deletions can be made.
  • What should be returned?
    • The function should return the root of the pruned tree.
HAPPY CASE
Input: 
    pothos1 = TreeNode("Healthy", TreeNode("Dying", TreeNode("Dying")), TreeNode("Healthy", TreeNode("Dying"), TreeNode("NewGrowth")))
    target = "Dying"
Output: 
    TreeNode("Healthy", None, TreeNode("Healthy", None, TreeNode("NewGrowth")))
Explanation: 
    The "Dying" nodes are pruned away, leaving a healthy tree.

EDGE CASE
Input: 
    pothos2 = TreeNode("Healthy", TreeNode("Aphids", TreeNode("Aphids", TreeNode("NewGrowth"))), TreeNode("Aphids"))
    target = "Aphids"
Output: 
    TreeNode("Healthy", TreeNode("Aphids", None, TreeNode("NewGrowth")), None)
Explanation: 
    The "Aphids" nodes are pruned, but the remaining "Aphids" with a child is not pruned.

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

  • Recursion: A recursive approach is natural here, as each node's children need to be examined and potentially pruned before deciding if the node itself should be pruned.
  • Postorder Traversal: Since the decision to prune a node depends on its children, a postorder traversal (left-right-root) ensures that child nodes are processed before their parents.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Perform a postorder traversal to prune the tree. Start by pruning the left and right subtrees, then determine if the current node should be pruned based on its value and whether it has become a leaf.

1) If the current node (`root`) is `None`, return `None`.
2) Recursively prune the left subtree by calling the `prune` function on `root.left`.
3) Recursively prune the right subtree by calling the `prune` function on `root.right`.
4) If the current node is a leaf (both left and right children are `None`) and its value is equal to `target`, return `None` to prune this node.
5) Return the current node (whether pruned or not).

⚠️ Common Mistakes

  • Forgetting to prune the node itself after pruning its children.
  • Incorrectly handling the recursion, leading to incorrect pruning of 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 prune(root, target):
    if not root:
        return None
    
    # Recursively prune the left and right subtrees
    root.left = prune(root.left, target)
    root.right = prune(root.right, target)
    
    # If the current node becomes a leaf with the target value, delete it
    if not root.left and not root.right and root.val == target:
        return None
    
    return root

5: R-eview

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

- Example 1:
    - Input: 
        `pothos1 = TreeNode("Healthy", TreeNode("Dying", TreeNode("Dying")), TreeNode("Healthy", TreeNode("Dying"), TreeNode("NewGrowth")))`
        `target = "Dying"`
    - Execution: 
        - Perform postorder traversal, pruning "Dying" nodes.
        - The final tree should only contain "Healthy" and "NewGrowth".
    - Output: 
        TreeNode("Healthy", None, TreeNode("Healthy", None, TreeNode("NewGrowth")))

- Example 2:
    - Input: 
        `pothos2 = TreeNode("Healthy", TreeNode("Aphids", TreeNode("Aphids", TreeNode("NewGrowth"))), TreeNode("Aphids"))`
        `target = "Aphids"`
    - Execution: 
        - Perform postorder traversal, pruning "Aphids" nodes.
        - The final tree should retain the "NewGrowth" node under "Aphids".
    - Output: 
        TreeNode("Healthy", TreeNode("Aphids", None, TreeNode("NewGrowth")), None)

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Time Complexity:

  • Time Complexity: O(N) where N is the number of nodes in the tree.
    • Explanation: We visit each node exactly once during the traversal.

Space Complexity:

  • Space Complexity: O(H) where H is the height of the tree.
    • Explanation: The recursion stack will use space proportional to the height H of the tree. In a balanced tree, H is O(log N), but in the worst case (skewed tree), it could be O(N).