---
description: '# Medium'
---

# 655. Print Binary Tree

{% hint style="info" %}
Key idea: compute the height of tree, build 2D array filled with  "", then use recursive to fill root.val, from root to leaf
{% endhint %}

{% tabs %}
{% tab title="Python" %}
```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def printTree(self, root: TreeNode) -> List[List[str]]:
        h = self.height(root)
        res = []
        for i in range(h):
            res.append(["" for i in range((1<<h) - 1)])
        self.fill(res, root, 0, 0, len(res[0])-1)
        return res
        
    def fill(self, res, root, i, l, r):
        if root == None:
            return
        res[i][(l+r)//2] = str(root.val)
        self.fill(res, root.left, i+1, l, (l+r)//2-1)
        self.fill(res, root.right, i+1, (l+r)//2+1, r)
        
    def height(self, root):
        if root == None:
            return 0
        return max(self.height(root.left), self.height(root.right)) + 1
```
{% endtab %}
{% endtabs %}

{% hint style="danger" %}
难点: recursive 中，fill左右两边时，不应该包括当前节点的那个index
{% endhint %}

Time = $$O(h*2^h)$$ ,  because of initilization,  Space = $$O(h*2^h)$$&#x20;
