Solution


Approach #1: Recursion [Accepted]

Intuition

Let trim(node) be the desired answer for the subtree at that node. We can construct the answer recursively.

Algorithm

When , we know that the trimmed binary tree must occur to the left of the node. Similarly, when , the trimmed binary tree occurs to the right of the node. Otherwise, we will trim both sides of the tree.

Complexity Analysis

  • Time Complexity: , where is the total number of nodes in the given tree. We visit each node at most once.

  • Space Complexity: . Even though we don't explicitly use any additional memory, the call stack of our recursion could be as large as the number of nodes in the worst case.


Analysis written by: @awice