We can easily get the dimensions of the ans, which is height and width of the tree, by DFS. The remaining work is to recursively preorder or other traversal of the tree.

Note a big number "1234567" takes the same space as "1". I misunderstood the question and came into a bit more complex problem.

Except initializing the answer of m row and n column, the run time is O(N). Here m is the height of the tree, n = 2^m-1, and N is how many nodes of the tree. In the worst case, for example, a tree with only left child, we have m = N, so the initialization is O(N x 2^N). Fortunately, m <= 10, so initialization is O(10000). When m is a big number, this can be an issue and we will have memory error as well.

Here I assume initialization using empty string is very fast. I did a test by adding the code below to show initialization is not the limiting factor.

```
vector<vector<string>> ans;
int k = 1000;
for (int i = 0; i < k; i++)
ans = vector<vector<string>>(h, vector<string>(w, ""));
```

k = 1, 3 ms;

k = 10, 3 ms;

k = 100, 9-12 ms;

k = 1000, ~70 ms;

So initialization seems huge, but only takes about 6-7% of total run time.

```
class Solution {
public:
vector<vector<string>> printTree(TreeNode* root) {
int h = get_height(root), w = get_width(root);
vector<vector<string>> ans(h, vector<string>(w, ""));
helper(ans, root, 0, 0, w-1);
return ans;
}
private:
int get_height(TreeNode* p) {
if (!p) return 0;
int left = get_height(p->left), right = get_height(p->right);
return max(left, right)+1;
}
// width is the max(left, right)*2+1
int get_width(TreeNode* p) {
if (!p) return 0;
int left = get_width(p->left), right = get_width(p->right);
return max(left, right)*2+1;
}
// always put the value in the middle of the range.
void helper(vector<vector<string>>& ans, TreeNode* p, int level, int l, int r) {
if (!p) return;
int mid = l+(r-l)/2;
ans[level][mid] = to_string(p->val);
helper(ans, p->left, level+1, l, mid-1);
helper(ans, p->right, level+1, mid+1, r);
}
};
```