Approach 1: Brute Force
Let's create every possible string - then we can compare them and choose the best one.
In our depth first search, we will maintain
A in Python), the contents of a path from the root to this node.
When we reach a leaf, we will reverse this path to create a candidate answer. If it is better than our current answer, we'll update our answer.
Time Complexity: We use to traverse the array and maintain
sb. Then, our reversal and comparison with the previous answer is , where is the size of the string we have when at the leaf. For example, for a perfectly balanced tree, and the time complexity would be .
Space Complexity: .