1
class Solution:
2
    def printTree(self, root: TreeNode) -> List[List[str]]:
3
        height = 0
4

5
        def dfs(node, h):  # Find height
6
            nonlocal height
7
            height = max(height, h)
8
            if node.left:
9
                dfs(node.left, h + 1)
10
            if node.right:
11
                dfs(node.right, h + 1)
12

13
        dfs(root, 0)
14
        n = 2 ** (height + 1) - 1  # Get `n`
15
        offset = (n - 1) // 2  # Column for root node
16
        ans = [[""] * n for _ in range(height + 1)]
17
        q = [(root, 0, offset)]
18
        for i in range(height + 1):  # BFS
19
            tmp_q = []
20
            while q:
21
                cur, r, c = q.pop()
22
                ans[r][c] = str(cur.val)
23
                if cur.left:
24
                    tmp_q.append((cur.left, r + 1, c - 2 ** (height - r - 1)))
25
                if cur.right:
26
                    tmp_q.append((cur.right, r + 1, c + 2 ** (height - r - 1)))
27
            q = tmp_q
28
        return ans