Solution
Approach 1: Brute Force
Intuition
Let's create every possible string  then we can compare them and choose the best one.
Algorithm
In our depth first search, we will maintain sb
(or 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.
Complexity Analysis

Time Complexity: We use to traverse the array and maintain
A
[Python] orsb
. 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: .
Analysis written by: @awice.