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.