If this is in sorted order, we know that this is valid. We can check this iterating through the returned list, checking that each iterated element's value is greater than the previous iteration's. If we get to the end, we can return True. If the opposite is ever true, we'll immediately return False.

Complexity of Final Solution

Let n be the size of the tree. We traverse through all n tree nodes using recursion for O(n) time complexity, and we have O(logn) space complexity due to recursion or O(d) where d is the depth of the tree.