print binary tree level by level in python

Question

I want to print my binary tree in the following manner:

                   10                 6        12               5   7    11  13  

I have written code for insertion of nodes but can't able to write for printing the tree. so please help on this . My code is :

class Node:     def __init__(self,data):        self.data=data        self.left=None        self.right=None        self.parent=None  class binarytree:    def __init__(self):      self.root=None      self.size=0     def insert(self,data):      if self.root==None:         self.root=Node(data)      else:         current=self.root         while 1:             if data < current.data:                 if current.left:                     current=current.left                 else:                     new=Node(data)                     current.left=new                     break;             elif data > current.data:                 if current.right:                     current=current.right                 else:                     new=Node(data)                     current.right=new                     break;             else:                 break     b=binarytree()   

Answer 1

Here's 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                                                         

Answer 2

What you're 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.