Binary Tree Pruning — Solution in Python, Java & C++
Binary Tree Pruning solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Binary Tree Pruning is a medium coding problem on depth-first search and trees, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Trees
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given the root of a binary tree in which every node holds 0 or 1. Remove every subtree that does not contain a 1, and return the root of what remains (an empty tree if nothing does).
The subtree of a node is the node together with all of its descendants.
Example 1
Input: root = [1,null,0,0,1]
Output: [1,null,0,null,1]
Explanation: The left child of the 0 is a lone 0 and is removed; the 0 itself stays because its subtree contains a 1.
Example 2
Input: root = [1,0,1,0,0,0,1]
Output: [1,null,1,null,1]
Explanation: The whole left subtree is zeros and goes; on the right only the path down to the last 1 survives.
Example 3
Input: root = [0,0,0]
Output: []
Explanation: No node holds a 1, so the entire tree is pruned away.
Constraints
The number of nodes in the tree is in the range [1, 200]Node.val is either 0 or 1
Hints for Binary Tree Pruning
Hint 1
Whether a node survives depends on its subtree — so decide for the children before deciding for the node.
Hint 2
Prune both children recursively first. Afterwards, a node with no remaining children survives only if it holds 1.
Hint 3
Return null for a pruned subtree and assign the results back to
leftandright; the root itself can disappear.
How to solve Binary Tree Pruning
A post-order walk prunes the children first; then a node is removable exactly when both its pruned children are empty and its own value is 0.
Approach
prune(node): return null for null.- Set
node.left = prune(node.left)andnode.right = prune(node.right). - If both are now null and
node.val == 0, return null; otherwise returnnode. - The answer is
prune(root).
Why it works
After pruning, a child subtree is non-empty exactly when it contains a 1 (by induction from the leaves). So a node's whole subtree lacks a 1 precisely when both pruned children are empty and the node is 0 — the case that returns null.
Complexity
- Time —
O(n) - Space —
O(h) for the recursion
Pitfalls
- Checking the node before pruning its children misses zero-leaves whose removal turns their parent into a removable zero-leaf.
- The root itself may be pruned — the result can be empty.
Reference solution
Python
from typing import Optional
def pruneTree(root: Optional[TreeNode]) -> Optional[TreeNode]:
if root is None:
return None
root.left = pruneTree(root.left)
root.right = pruneTree(root.right)
if root.left is None and root.right is None and root.val == 0:
return None
return rootJava
public static TreeNode pruneTree(TreeNode root) {
if (root == null) return null;
root.left = pruneTree(root.left);
root.right = pruneTree(root.right);
if (root.left == null && root.right == null && root.val == 0) return null;
return root;
}C++
TreeNode* pruneTree(TreeNode* root) {
if (!root) return nullptr;
root->left = pruneTree(root->left);
root->right = pruneTree(root->right);
if (!root->left && !root->right && root->val == 0) return nullptr;
return root;
}JavaScript
var pruneTree = function(root) {
if (root === null) return null;
root.left = pruneTree(root.left);
root.right = pruneTree(root.right);
if (root.left === null && root.right === null && root.val === 0) return null;
return root;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals