Binary Tree Pruning - Solution & Explanation
Problem Statement
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.
Example 1:
Input: root = [1,null,0,0,1] Output: [1,null,0,null,1] Explanation: Only the red nodes satisfy the property "every subtree not containing a 1". The diagram on the right represents the answer.
Example 2:
Input: root = [1,0,1,0,0,0,1] Output: [1,null,1,null,1]
Example 3:
Input: root = [1,1,0,1,1,0,1,0] Output: [1,1,0,1,1,null,1]
Constraints:
- The number of nodes in the tree is in the range
[1, 200]. Node.valis either0or1.
Approach Overview
Problem Overview: Given a binary tree containing only 0 and 1, remove every subtree that does not contain a 1. If a subtree is made entirely of zeros, it should be pruned from the parent. The result is a modified tree where every remaining subtree contains at least one 1.
Approach 1: Post-order Traversal (DFS) (Time: O(n), Space: O(h))
The cleanest solution uses post-order traversal with recursion. In post-order, you process the left and right children before evaluating the current node. This order is critical because whether a node should be pruned depends on whether its children contain a 1. Recursively prune the left subtree and assign the result to root.left, then do the same for the right subtree. After both recursive calls return, check the current node: if root.val == 0 and both children are null, the entire subtree contains only zeros and should be removed by returning null.
This approach works because every subtree is evaluated bottom-up. By the time you process a node, its children have already been cleaned. The algorithm visits each node exactly once, giving O(n) time complexity where n is the number of nodes. Recursion depth depends on tree height, so the space complexity is O(h). This method relies on classic Depth-First Search over a Binary Tree, making it both concise and interview-friendly.
Approach 2: Iterative Post-order Traversal (Time: O(n), Space: O(h))
The same pruning logic can be implemented iteratively using an explicit stack to simulate post-order traversal. Maintain a stack of nodes along with a visited flag or use two-stack traversal. The goal is to ensure children are processed before their parent. Once both children of a node have been handled, check whether they were pruned and determine if the current node should also be removed.
This approach avoids recursion and is useful in environments where recursion depth may exceed stack limits. Each node is pushed and popped from the stack at most once, so the total runtime remains O(n). Auxiliary stack space grows with the height of the tree, resulting in O(h) space complexity. The underlying idea is still the same bottom-up evaluation commonly used in Tree dynamic processing problems.
Recommended for interviews: The recursive post-order traversal is the expected solution. It expresses the pruning rule directly: process children first, then decide whether the current node survives. Interviewers typically look for this bottom-up reasoning because it shows you understand how subtree information flows upward. The iterative version demonstrates deeper knowledge of traversal mechanics but is rarely required unless recursion limits are discussed.
Approach 1: Approach 1: Post-order Traversal
This approach uses post-order traversal to traverse each subtree and decide if it should be pruned. Starting from the leaf nodes, it recursively checks if a subtree contains a 1. If a subtree doesn't contain any 1s, it returns null. This way, when the recursion unwinds, only relevant subtrees are kept.
The provided C code represents a function that conducts a post-order traversal starting from the given root node. It uses recursion to visit each node, first addressing the left and right subtrees. If a node's value is 0 and both its subtrees are NULL, the node is pruned by freeing its memory and returning NULL. Otherwise, the node is returned intact. The traversal ensures all subtrees without a 1 are effectively pruned away.
Complexity
Time Complexity: O(N), where N is the number of nodes, since each node is visited once.
Space Complexity: O(H), where H is the height of the tree, due to the recursive stack space.
Approach 2: Approach 2: Iterative Post-order Traversal
By utilizing an iterative traversal using a stack, the tree can be pruned without recursion. This approach mimics the recursion stack by using an explicit stack to manage nodes that need to be processed. Once the subtree rooted at a node is evaluated, decisions are made to prune or retain nodes based on whether a 1 is found.
The C implementation employs a boolean helper function, containsOne, which verifies if any subtree contains the value 1. The iterative sense is simulated by the helper function instead of explicit stack management. Nodes without 1 in their subtrees are trimmed, promoting a structured pruning process.
Complexity
Time Complexity: O(N), as we are ensuring every node is visited.
Space Complexity: O(H), attributed to the height of the tree in terms of stack use.
Approach 3: Recursion
First, we check if the current node is null. If it is, we directly return the null node.
Otherwise, we recursively prune the left and right subtrees and reassign the pruned subtrees to the current node's left and right children. Then, we check if the current node's value is 0 and both its left and right children are null. If so, we return the null node; otherwise, we return the current node.
Time complexity is O(n), and space complexity is O(n). Here, n is the number of nodes in the binary tree.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Post-order Traversal | Time Complexity: O(N), where N is the number of nodes, since each node is visited once. |
| Approach 2: Iterative Post-order Traversal | Time Complexity: O(N), as we are ensuring every node is visited. |
| Recursion | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Post-order Traversal | O(n) | O(h) | Best general solution. Clean recursive logic and commonly expected in interviews. |
| Iterative Post-order Traversal | O(n) | O(h) | Useful when recursion depth may be large or recursion is restricted. |
Video Solution
Binary Tree Pruning | LeetCode 814 | C++, Java, Python • Knowledge Center • 3,304 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Binary Tree Pruning easy or hard?
How to solve Binary Tree Pruning in O(n)?
Binary Tree Pruning Python or Java solution?
What is the best approach for Binary Tree Pruning?
Is Binary Tree Pruning asked at Google/Amazon/Meta?
What data structure is used in Binary Tree Pruning?
What is the time complexity of Binary Tree Pruning?
Ready to solve this problem?
Practice Binary Tree Pruning with our built-in code editor and test cases.
Practice on FleetCode