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

Leave a Reply

Your email address will not be published. Required fields are marked *