Level order traversal using queue in python

Python program for Level order traversal using queue. Here problem description and explanation.

#  Python 3 program for
#  Level order tree traversal using queue

#  Create Q node
class QNode :
	def __init__(self, node) :
		self.data = node
		self.next = None
	

#  Binary Tree Node
class TreeNode :
	def __init__(self, data) :
		#  Set node value
		self.data = data
		self.left = None
		self.right = None
	

class MyQueue :
	def __init__(self) :
		self.head = None
		self.tail = None
		self.count = 0
	
	def size(self) :
		return self.count
	
	def isEmpty(self) :
		return self.count == 0
	
	#  Add new node of queue
	def enqueue(self, value) :
		#  Create a new node
		node = QNode(value)
		if (self.head == None) :
			#  Add first element into queue
			self.head = node
		else :
			#  Add node at the end using tail
			self.tail.next = node
		
		self.count += 1
		self.tail = node
	
	#  Delete a element into queue
	def dequeue(self) :
		if (self.head == None) :
			#  Empty Queue
			return
		
		#  Visit next node
		self.head = self.head.next
		self.count -= 1
		if (self.head == None) :
			#  When deleting a last node of linked list
			self.tail = None
		
	
	#  Get front node
	def peek(self) :
		if (self.head == None) :
			return None
		
		return self.head.data
	

class BinaryTree :
	def __init__(self) :
		self.root = None
	
	def levelOrder(self) :
		if (self.root != None) :
			q = MyQueue()
			#  Add first node
			q.enqueue(self.root)
			node = self.root
			while (q.isEmpty() == False and node != None) :
				if (node.left != None) :
					#  Add left child node
					q.enqueue(node.left)
				
				if (node.right != None) :
					#  Add right child node
					q.enqueue(node.right)
				
				#  Display level node
				print(node.data, end = "  ")
				#  Remove current node
				q.dequeue()
				#  Get new head
				node = q.peek()
			
		else :
			print("Empty Tree")
		
	

def main() :
	#  Create new tree
	tree = BinaryTree()
	#  Make A Binary Tree
	#  -----------------------
	#         1
	#       /   \
	#      2     3
	#     /     / \
	#    4     5   6
	#   /     / \
	#  7     8   9
	#  Adding tree nodes
	tree.root = TreeNode(1)
	tree.root.left = TreeNode(2)
	tree.root.right = TreeNode(3)
	tree.root.right.right = TreeNode(6)
	tree.root.right.left = TreeNode(5)
	tree.root.left.left = TreeNode(4)
	tree.root.left.left.left = TreeNode(7)
	tree.root.right.left.left = TreeNode(8)
	tree.root.right.left.right = TreeNode(9)
	#  Display level order element
	tree.levelOrder()

if __name__ == "__main__": main()

Output

1  2  3  4  5  6  7  8  9



Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2022, kalkicode.com, All rights reserved