May 22, 2016

Level order traversal of Binary tree in Python

Level order traversal in python
Input:-
     5 
   3     7
2    4  6   8
Level order traversal of BST:  5 3 7 2 4 6 8
import sys

class Node:
    def __init__(self,data):
        self.right=self.left=None
        self.data = data
class Solution:
    def insert(self,root,data):
        if root==None:
            return Node(data)
        else:
            if data<=root.data:
                cur=self.insert(root.left,data)
                root.left=cur
            else:
                cur=self.insert(root.right,data)
                root.right=cur
        return root
    def levelOrder(self,root):
        items = []
        count=0
        items.insert(count,root)
        elements =""
        while items != []:
            temp = items.pop()
            elements= elements+str(temp.data)+ " "
            if temp.left!=None:
                items.insert(0,temp.left)
            if temp.right!=None:
                items.insert(0,temp.right)
        print "Level order traversal of BST: "+ elements 
print "Enter numer of elements to be added in tree: "  
N=int(raw_input())
myTree=Solution()
root=None
print "Enter elements: "
for i in range(N):
    data=int(raw_input())
    root=myTree.insert(root,data)
myTree.levelOrder(root)
Sampel output:-
>>>
7
5
3
7
2
4
6
8
Level order traversal of BST: 5 3 7 2 4 6 8
Location: Hyderabad, Telangana, India