Approach #1: Recursion [Accepted]
Prune children of the tree recursively. The only decisions at each node are whether to prune the left child or the right child.
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
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.
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.