# print binary tree level by level in python

## print binary tree level by level in python

Heres my attempt, using recursion, and keeping track of the size of each node and the size of children.

``````class BstNode:

def __init__(self, key):
self.key = key
self.right = None
self.left = None

def insert(self, key):
if self.key == key:
return
elif self.key < key:
if self.right is None:
self.right = BstNode(key)
else:
self.right.insert(key)
else: # self.key > key
if self.left is None:
self.left = BstNode(key)
else:
self.left.insert(key)

def display(self):
lines, *_ = self._display_aux()
for line in lines:
print(line)

def _display_aux(self):
Returns list of strings, width, height, and horizontal coordinate of the root.
# No child.
if self.right is None and self.left is None:
line = %s % self.key
width = len(line)
height = 1
middle = width // 2
return [line], width, height, middle

# Only left child.
if self.right is None:
lines, n, p, x = self.left._display_aux()
s = %s % self.key
u = len(s)
first_line = (x + 1) *   + (n - x - 1) * _ + s
second_line = x *   + / + (n - x - 1 + u) *
shifted_lines = [line + u *   for line in lines]
return [first_line, second_line] + shifted_lines, n + u, p + 2, n + u // 2

# Only right child.
if self.left is None:
lines, n, p, x = self.right._display_aux()
s = %s % self.key
u = len(s)
first_line = s + x * _ + (n - x) *
second_line = (u + x) *   + \ + (n - x - 1) *
shifted_lines = [u *   + line for line in lines]
return [first_line, second_line] + shifted_lines, n + u, p + 2, u // 2

# Two children.
left, n, p, x = self.left._display_aux()
right, m, q, y = self.right._display_aux()
s = %s % self.key
u = len(s)
first_line = (x + 1) *   + (n - x - 1) * _ + s + y * _ + (m - y) *
second_line = x *   + / + (n - x - 1 + u + y) *   + \ + (m - y - 1) *
if p < q:
left += [n *  ] * (q - p)
elif q < p:
right += [m *  ] * (p - q)
zipped_lines = zip(left, right)
lines = [first_line, second_line] + [a + u *   + b for a, b in zipped_lines]
return lines, n + m + u, max(p, q) + 2, n + u // 2

import random

b = BstNode(50)
for _ in range(50):
b.insert(random.randint(0, 100))
b.display()
``````

Example output:

``````                              __50_________________________________________
/
________________________43_                   ________________________99
/                                            /
_9_                         48    ____________67_____________________
/                                /
3  11_________                   54___                         ______96_
/                                                           /
0 8       ____26___________           61___           ________88___     97
/                          /              /
14_             __42        56    64_       75_____       92_
/              /                 /        /            /
13  16_         33_               63  65_   72      81_   90  94
/                                 /
25    __31  41                    66        80  87
/                                     /
28_                                   76

29
``````

What youre looking for is breadth-first traversal, which lets you traverse a tree level by level. Basically, you use a queue to keep track of the nodes you need to visit, adding children to the back of the queue as you go (as opposed to adding them to the front of a stack). Get that working first.

After you do that, then you can figure out how many levels the tree has (`log2(node_count) + 1`) and use that to estimate whitespace. If you want to get the whitespace exactly right, you can use other data structures to keep track of how many spaces you need per level. A smart estimation using number of nodes and levels should be enough, though.

#### print binary tree level by level in python

``````class Node(object):
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right

def printTree(node, level=0):
if node != None:
printTree(node.left, level + 1)
print(  * 4 * level + ->  + node.value)
printTree(node.right, level + 1)

t = Node(1, Node(2, Node(4, Node(7)),Node(9)), Node(3, Node(5), Node(6)))
printTree(t)
``````

output:

``````            -> 7
-> 4
-> 2
-> 9
-> 1
-> 5
-> 3
-> 6
``````