Problem statement

https://leetcode.com/problems/print-binary-tree/

Solution

Note at first, that the size of our array will be H x (2^H-1). So, first of all let us find height and create empty array. Then we use recursion function fill(node, x, y, step), where x and y are coordinates we need to fill and step is step we need to make to go to the left or to the right; step should be decreased twice each step.

Complexity

It is O(h * 2^h) for time and space, because this is the size of our output.

Code

class Solution:
    def printTree(self, root):
        def dfs(node):
            if not node: return 0
            return max(dfs(node.left), dfs(node.right)) + 1
        
        def fill(node, x, y, step):
            if not node: return
            ans[y][x] = str(node.val)
            fill(node.left,  x-step, y+1, step>>1)
            fill(node.right, x+step, y+1, step>>1)
        
        H = dfs(root)
        W = 1<<H
        ans = [[""] * (W-1) for _ in range(H)]
        fill(root, (W>>1)-1, 0, W>>2)
        return ans