We can determine the width of the print result by applying this formula: # of max nodes in the maximum depth + cumulative sum of nodes from levels before. This essentially then becomes 2 ** max_depth - 1 due to the nature of binary trees. After we figure out the structure of the grid, we just need to recursively fill in this grid by grabbing the mid position for each recursive call. This is again due to the nature of how binary trees are structured: each node is the root of a subtree and each node will split into two nodes except for the last level.
def printTree(self, root): def max_depth(root): # method for getting max depth if not root: return 0 return max(max_depth(root.left), max_depth(root.right)) + 1 def fill_grid(root, grid, lv, i, j): # recursive method for filling predetermined grid if root: m = i + (j-i) // 2 # mid point grid[lv][m] = str(root.val); lv += 1 # lv ++ fill_grid(root.left, grid, lv, i, m-1) # left child fill_grid(root.right, grid, lv, m+1, j) # right child d = max_depth(root) width = (1 << d) - 1 # width of printed result grid = [['' for _ in range(width)] for _ in range(d)] fill_grid(root, grid, 0, 0, width-1) return grid