title: Binary Tree Pruning
slug: binary-tree-pruning
difficulty: medium
leetcode_id: 814
leetcode_url: https://leetcode.com/problems/binary-tree-pruning/
categories:
  - trees
  - recursion
patterns:
  - slug: dfs
    is_optimal: true
  - slug: tree-traversal
    is_optimal: false

function_signature: "def prune_tree(root: TreeNode) -> TreeNode:"

test_cases:
  visible:
    - input: { root: [1, null, 0, 0, 1] }
      expected: [1, null, 0, null, 1]
    - input: { root: [1, 0, 1, 0, 0, 0, 1] }
      expected: [1, null, 1, null, 1]
    - input: { root: [1, 1, 0, 1, 1, 0, 1, 0] }
      expected: [1, 1, 0, 1, 1, null, 1]
  hidden:
    - input: { root: [1] }
      expected: [1]
    - input: { root: [0] }
      expected: null
    - input: { root: [0, 0, 0] }
      expected: null
    - input: { root: [1, 1, 1, 1, 1, 1, 1] }
      expected: [1, 1, 1, 1, 1, 1, 1]
    - input: { root: [0, 0, 0, 1] }
      expected: [0, 0, null, 1]
    - input: { root: [1, 0, 0, 0, 0, 0, 1] }
      expected: [1, null, 0, null, 1]

description: |
  Given the `root` of a binary tree, return *the same tree where every subtree (of the given tree) not containing a* `1` *has been removed*.

  A subtree of a node `node` is `node` plus every node that is a descendant of `node`.

constraints: |
  - `1 <= number of nodes <= 200`
  - `Node.val` is either `0` or `1`

examples:
  - input: "root = [1,null,0,0,1]"
    output: "[1,null,0,null,1]"
    explanation: "Only nodes that are part of a subtree containing a 1 are kept. The left child of the 0 node (which was 0) is removed since that subtree contains no 1s."
  - input: "root = [1,0,1,0,0,0,1]"
    output: "[1,null,1,null,1]"
    explanation: "The entire left subtree of the root (rooted at 0) is removed because it contains no 1s. The left subtree of the right child (also 0) is removed for the same reason."
  - input: "root = [1,1,0,1,1,0,1,0]"
    output: "[1,1,0,1,1,null,1]"
    explanation: "Most of the tree is preserved since there are 1s throughout. Only the leftmost leaf (0) and one subtree containing only 0s are pruned."

explanation:
  intuition: |
    Imagine you're a gardener pruning a tree. You need to remove all branches that don't bear any fruit (in this case, nodes with value `1`). But here's the catch: you can only tell if a branch is fruitful by checking the entire branch, all the way down to the leaves.

    The key insight is that **you must check the children before deciding about the parent**. A node should be kept if:
    1. It has value `1`, OR
    2. At least one of its children (after pruning) still exists

    Think of it like this: start at the leaves and work your way up. A leaf node with value `0` can be removed. But a node with value `0` that has a child containing a `1` somewhere must stay — it's the path to that `1`.

    This naturally leads to a **post-order traversal** (left, right, node): process children first, then decide about the current node based on what remains.

  approach: |
    We solve this using **Post-Order DFS (Depth-First Search)**:

    **Step 1: Define the recursive function**

    - The function takes a node and returns either the pruned node or `None` if the entire subtree should be removed
    - Base case: if the node is `None`, return `None`

    &nbsp;

    **Step 2: Recursively prune children**

    - First, recursively prune the left subtree: `node.left = prune(node.left)`
    - Then, recursively prune the right subtree: `node.right = prune(node.right)`
    - This is the "post-order" part — we handle children before the current node

    &nbsp;

    **Step 3: Decide whether to keep the current node**

    - After pruning children, check if this node should be removed
    - Remove the node (return `None`) if ALL of these are true:
      - `node.val == 0` (node itself doesn't contain a 1)
      - `node.left is None` (left subtree was fully pruned)
      - `node.right is None` (right subtree was fully pruned)
    - Otherwise, keep the node (return `node`)

    &nbsp;

    **Step 4: Handle the root**

    - Call the recursive function on the root
    - The root itself might be pruned if the entire tree contains no 1s

    &nbsp;

    The post-order traversal ensures we always have complete information about children before deciding about the parent.

  common_pitfalls:
    - title: Pre-Order Instead of Post-Order
      description: |
        A common mistake is trying to decide about a node before processing its children:

        ```python
        # WRONG: checking node before children
        if node.val == 0:
            return None  # But what if children have 1s?
        ```

        This fails because a `0` node might be the parent of a subtree containing `1`s. You must process children first (post-order) to know if they contain any `1`s.
      wrong_approach: "Check node value before recursing on children"
      correct_approach: "Recurse on children first, then decide about current node"

    - title: Forgetting to Update Child Pointers
      description: |
        After recursively pruning, you must update the parent's pointers:

        ```python
        # WRONG: not updating pointers
        prune(node.left)
        prune(node.right)

        # CORRECT: update the pointers
        node.left = prune(node.left)
        node.right = prune(node.right)
        ```

        Without updating pointers, the tree structure isn't actually modified — pruned subtrees remain connected.
      wrong_approach: "Call recursive function without assigning result"
      correct_approach: "Assign recursive result back to node.left/node.right"

    - title: Not Handling the Root Being Pruned
      description: |
        The root itself might need to be removed if the entire tree contains no `1`s:

        ```python
        # Example: root = [0, 0, 0]
        # After pruning, the entire tree should become None
        ```

        Make sure your solution can return `None` for the root, not just for subtrees. The recursive structure naturally handles this if implemented correctly.

  key_takeaways:
    - "**Post-order traversal pattern**: When a decision depends on children's state, process children first (left → right → node)"
    - "**Recursive tree modification**: Update child pointers with the result of recursive calls to actually modify the tree structure"
    - "**Condition for keeping a node**: A node survives if it has value `1` OR has at least one surviving child"
    - "**Foundation for tree problems**: This pattern of 'decide based on children' appears in many tree problems like finding tree diameter, checking balance, or computing heights"

  time_complexity: "O(n). We visit each node exactly once during the DFS traversal, where `n` is the number of nodes in the tree."
  space_complexity: "O(h). The recursion stack can grow up to `h` frames deep, where `h` is the height of the tree. In the worst case (skewed tree), `h = n`. For a balanced tree, `h = log(n)`."

solutions:
  - approach_name: Post-Order DFS
    is_optimal: true
    code: |
      class TreeNode:
          def __init__(self, val=0, left=None, right=None):
              self.val = val
              self.left = left
              self.right = right

      def prune_tree(root: TreeNode | None) -> TreeNode | None:
          # Base case: empty tree
          if root is None:
              return None

          # Post-order: process children first
          # Update left subtree with pruned result
          root.left = prune_tree(root.left)
          # Update right subtree with pruned result
          root.right = prune_tree(root.right)

          # Now decide about current node
          # Remove if: value is 0 AND both children are gone
          if root.val == 0 and root.left is None and root.right is None:
              return None

          # Keep this node
          return root
    explanation: |
      **Time Complexity:** O(n) — We visit each node exactly once.

      **Space Complexity:** O(h) — Recursion stack depth equals tree height.

      The post-order traversal guarantees that when we examine a node, both its children have already been pruned. This gives us complete information to decide: if the node is `0` and has no remaining children, it can be safely removed.

  - approach_name: Iterative with Parent Tracking
    is_optimal: false
    code: |
      def prune_tree(root: TreeNode | None) -> TreeNode | None:
          if root is None:
              return None

          # Use stack for post-order traversal
          # Store (node, parent, is_left_child, visited_children)
          stack = [(root, None, None, False)]

          while stack:
              node, parent, is_left, visited = stack[-1]

              if not visited:
                  # First visit: mark as visited, add children
                  stack[-1] = (node, parent, is_left, True)
                  if node.right:
                      stack.append((node.right, node, False, False))
                  if node.left:
                      stack.append((node.left, node, True, False))
              else:
                  # Second visit: children processed, decide about this node
                  stack.pop()

                  # Should this node be pruned?
                  should_prune = (
                      node.val == 0 and
                      node.left is None and
                      node.right is None
                  )

                  if should_prune and parent:
                      # Remove from parent
                      if is_left:
                          parent.left = None
                      else:
                          parent.right = None
                  elif should_prune and parent is None:
                      # Root should be pruned
                      return None

          return root
    explanation: |
      **Time Complexity:** O(n) — Each node is pushed and popped from the stack once.

      **Space Complexity:** O(n) — Stack can hold all nodes in worst case.

      This iterative approach simulates post-order traversal using a stack with parent tracking. While it avoids recursion, it's more complex and uses more space due to storing parent references. The recursive solution is preferred for its clarity.
