How do you solve Binary Tree Pruning on LeetCode?

Binary Tree Pruning (LeetCode #814) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(h) space complexity. Key insight: Pruning a tree requires careful consideration of child nodes and their values.

What is the brute force solution for Binary Tree Pruning?

The brute force approach for Binary Tree Pruning is Brute Force, with O(n²) time complexity and O(1) space complexity. In the brute-force approach, we traverse the entire tree and check each subtree to see if it contains a '1'. If it doesn't, we remove that subtree. This is straightforward but inefficient because we may end up checking the same nodes multiple times. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Binary Tree Pruning?

Binary Tree Pruning uses the following concepts: Tree, Depth-First Search, Binary Tree. The recommended patterns to study are: Depth-First Search, Tree Traversal.

What are the interview tips for Binary Tree Pruning?

Always clarify the problem statement and constraints before diving into coding. Think about edge cases, such as trees with only '0's or only '1's. Discuss your thought process and approach with the interviewer before writing code.

What are common mistakes when solving Binary Tree Pruning?

Not handling null nodes properly, which can lead to null pointer exceptions. Failing to return the modified tree correctly, leading to incorrect outputs.

#814

Binary Tree Pruning

Medium

TreeDepth-First SearchBinary TreeDepth-First SearchTree Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(h)

💡

Intuition

Time O(n)Space O(h)

The optimal approach uses a depth-first search to prune the tree in a single pass. We check if each subtree contains a '1' and prune it accordingly, which allows us to avoid unnecessary checks and achieve linear time complexity.

⚙️

Algorithm

4 steps

1Step 1: Perform a depth-first search on the tree.
2Step 2: Recursively check the left and right children of each node.
3Step 3: If a child subtree does not contain a '1', set that child to null.
4Step 4: Return the current node if it contains a '1' or if any of its children do.

solution.py15 lines

1# Full working Python code
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8def pruneTree(root):
9    if not root:
10        return None
11    root.left = pruneTree(root.left)
12    root.right = pruneTree(root.right)
13    if root.val == 0 and not root.left and not root.right:
14        return None
15    return root

ℹ

Complexity note: The time complexity is O(n) because we visit each node exactly once. The space complexity is O(h) due to the recursion stack, where h is the height of the tree.

1Pruning a tree requires careful consideration of child nodes and their values.
2Using depth-first search allows us to efficiently traverse and modify the tree in one pass.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.