Approach #1: Recursion [Accepted]
Intuition
Prune children of the tree recursively. The only decisions at each node are whether to prune the left child or the right child.
Algorithm
We'll use a function containsOne(node)
that does two things: it tells us whether the subtree at this node
contains a 1
, and it also prunes all subtrees not containing 1
.
If for example, node.left
does not contain a one, then we should prune it via node.left = null
.
Also, the parent needs to be checked. If for example the tree is a single node 0
, the answer is an empty tree.
Complexity Analysis

Time Complexity: , where is the number of nodes in the tree. We process each node once.

Space Complexity: , where is the height of the tree. This represents the size of the implicit call stack in our recursion.
Analysis written by: @awice.