# Python BFS solution using queue, no recursion.

• The idea is straightforward,

1. calculate the height, so the column n will be pow(2, h)-1
2. for each row, it will have count=pow(2, i) numbers so each number will take n / count space, because we need to put them in the middle of their space so the first of each row postion is n / count / 2, the next one will be n / count / 2 + n / count + 1 on the right side, then next next is n / count / 2 + n / count + 1 + n / count + 1 .... so we can conclude the position of number j in each row is: n / count / 2 + j * (n / count + 1) here each time add 1 because their direct parent will take up one space (see problem example 1, 2nd row is '2', '', '', the middle '' is taken by previous '1'
3. just put the number in their position and append each row to the final result
``````class Solution(object):
def getHeight(self, root):
if root is None:
return 0
return 1 + max(self.getHeight(root.left), self.getHeight(root.right))

def printTree(self, root):
"""
:type root: TreeNode
:rtype: List[List[str]]
"""
res = []
h = self.getHeight(root)
n = pow(2, h) - 1
q = [root]
for i in range(0, h):
lvl = [''] * n
count = pow(2, i)
for j in range(0, count):
top = q.pop(0)
pos = j * (n / count + 1) + n / count / 2
val = ''
left = None
right = None
if top is not None:
val = str(top.val)
left = top.left
right = top.right
lvl[pos] = val
q.append(left)
q.append(right)
res.append(lvl)
return res
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.