## Print Binary Tree

• Time:O(h \cdot 2^h)
• Space:O(h \cdot 2^h)

## C++

class Solution {
public:
vector<vector<string>> printTree(TreeNode* root) {
const int m = maxHeight(root);
const int n = pow(2, m) - 1;
vector<vector<string>> ans(m, vector<string>(n));
dfs(root, 0, 0, ans[0].size() - 1, ans);
return ans;
}

private:
int maxHeight(TreeNode* root) {
if (!root)
return 0;
return 1 + max(maxHeight(root->left), maxHeight(root->right));
}

void dfs(TreeNode* root, int row, int left, int right,
vector<vector<string>>& ans) {
if (!root)
return;

const int mid = (left + right) / 2;
ans[row][mid] = to_string(root->val);
dfs(root->left, row + 1, left, mid - 1, ans);
dfs(root->right, row + 1, mid + 1, right, ans);
}
};


## JAVA

class Solution {
public List<List<String>> printTree(TreeNode root) {
final int m = maxHeight(root);
final int n = (int) Math.pow(2, m) - 1;
List<List<String>> ans = new ArrayList<>();
List<String> row = new ArrayList<>();

for (int i = 0; i < n; ++i)

for (int i = 0; i < m; ++i)

dfs(root, 0, 0, n - 1, ans);
return ans;
}

private int maxHeight(TreeNode root) {
if (root == null)
return 0;
return 1 + Math.max(maxHeight(root.left), maxHeight(root.right));
}

private void dfs(TreeNode root, int row, int left, int right, List<List<String>> ans) {
if (root == null)
return;

final int mid = (left + right) / 2;
ans.get(row).set(mid, Integer.toString(root.val));
dfs(root.left, row + 1, left, mid - 1, ans);
dfs(root.right, row + 1, mid + 1, right, ans);
}
}


## Python

class Solution:
def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:
def maxHeight(root: Optional[TreeNode]) -> int:
if not root:
return 0
return 1 + max(maxHeight(root.left), maxHeight(root.right))

def dfs(root: Optional[TreeNode], row: int, left: int, right: int) -> None:
if not root:
return

mid = (left + right) // 2
ans[row][mid] = str(root.val)
dfs(root.left, row + 1, left, mid - 1)
dfs(root.right, row + 1, mid + 1, right)

m = maxHeight(root)
n = pow(2, m) - 1
ans = [[''] * n for _ in range(m)]
dfs(root, 0, 0, len(ans[0]) - 1)
return ans