Traversing a binary tree in level order in python

Question

I have a python script that generate a binary tree for a given mathematical expression. I'm trying to write a function to print the binary tree if I traverse it in the level-order.

e.g. if the function is ((2+3) - 4) the output should be

   -
  / \
 +   4
/ \
2  3

output: 
-
+ 4
2 3

Code to convert the mathematical expression into a binary tree

from pythonds.basic.stack import Stack
from pythonds.trees.binaryTree import BinaryTree

def buildParseTree(fpexp):
        fplist = fpexp.split()
        pStack = Stack()
        eTree = BinaryTree('')
        pStack.push(eTree)
        currentTree = eTree
        for i in fplist:
            if i == '(':
                currentTree.insertLeft('')
                pStack.push(currentTree)
                currentTree = currentTree.getLeftChild()
            elif i not in ['+', '-', '*', '/', ')']:
                currentTree.setRootVal(int(i))
                parent = pStack.pop()
                currentTree = parent
            elif i in ['+', '-', '*', '/']:
                currentTree.setRootVal(i)
                currentTree.insertRight('')
                pStack.push(currentTree)
                currentTree = currentTree.getRightChild()
            elif i == ')':
                currentTree = pStack.pop()
            else:
                raise ValueError
        return eTree

I'm using the standard pseudo-code for the breadth-first search.

printTree(Node root)

   if(root == NULL) return

   else
      create a queue 'q'
      q.enqueue(root)

      while(q is not empty)
           root = q.dequeue
           print(root)

           if(leftChild != NULL)
              q.enqueue(leftChild)
           if(rightChild != NULL)
              q.enqueue(rightChild)

Following is the python code I wrote to print the tree in level-order.

import sys

class Node:
    def __init__(self, data):
        self.data = data
        self.leftChild = None
        self.rightChid = None


class Queue:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def enqueue(self,item):
        self.items.insert(0, item)

    def dequeue(self):
        self.items.pop()

def printNodesInLevels(root):
    if root is None:
        return
    else:
        q = Queue()
        q.enqueue(root)

        while(q is not None):
            root = q.dequeue()
            print(root.getRootVal())

            if(root.leftChild is not None):
                q.enqueue(root.leftChild)

            if(root.rightChild is not None):
                q.enqueue(root.rightChild)

This is how I invoke the function.

pt = buildParseTree("( ( 2 + 3 ) - 4 )")
printNodesInLevels(pt)

Following is the error message I'm getting. I think I'm not passing the root of the tree to the print function properly.

None

Traceback (most recent call last): File "C:/Users/YASODA/PycharmProjects/HelloWorld/BinaryTree.py", line 77, in printNodesInLevels(pt) File "C:/Users/YASODA/PycharmProjects/HelloWorld/BinaryTree.py", line 67, in printNodesInLevels if(root.leftChild is not None): AttributeError: 'NoneType' object has no attribute 'leftChild'

Do you mean whether pt encodes the tree correctly? Yes it does. pt.inorder() will print the tree in inorder — SriniShine
Ok also I do not see root.getRootVal() appear anywhere in code, only in your error message — Skyler
@Skyler sorry. I pasted the wrong error message. Now I updated the question. — SriniShine

Skyler Skyler · Accepted Answer · 2018-02-14T16:23:49

There are two mistakes in your code. The first one is, you need to return in dequeue,

class Queue:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def enqueue(self,item):
        self.items.insert(0, item)

    def dequeue(self):
        return self.items.pop()

Second one is in the while loop check if the queue is empty,

while(not q.isEmpty()):

Traversing a binary tree in level order in python

1 Answers