Binary Tree Pruning
Medium · Trees · Tree · Depth-First Search · Binary Tree
Problem
Every node of a binary tree holds 0 or 1. Remove every subtree that contains no 1, and return the root of the pruned tree.
The subtree of a node is that node together with all of its descendants. If the whole tree contains no 1, the result is the empty tree.
Trees are shown as level-order lists, with null for a missing child.
Examples
Input: root = [0,1,0,0,0,null,1] Output: [0,1,0,null,null,null,1]
Both children of the left 1 are zeros with nothing below them, so they go. The right 0 stays because a 1 hangs under it, and the root stays because 1s are below it.
Input: root = [0,0,0] Output: []
There is no 1 anywhere, so everything is removed.
Constraints
- 1 <= number of nodes <= 200
- Node.val is 0 or 1
Approaches
- Search each subtree for a 1 — time O(n²), space O(h)
Follow-up
What if values can be any integers and you must remove every subtree whose values sum to 0? The same post-order works: each call returns its subtree sum and the pruned subtree. Only the removal test changes.
Related problems
Start free on Cariara · Coding problems · System design studio
