Level order traversal using queue in ruby

Ruby program for Level order traversal using queue. Here more information.

#  Ruby program for
#  Level order tree traversal using queue

#  Create Q node
class QNode 
	# Define the accessor and reader of class QNode
	attr_reader :data, :next
	attr_accessor :data, :next
	def initialize(node) 
		self.data = node
		self.next = nil
	end
end

#  Binary Tree Node
class TreeNode 
	# Define the accessor and reader of class TreeNode
	attr_reader :data, :left, :right
	attr_accessor :data, :left, :right
	def initialize(data) 
		#  Set node value
		self.data = data
		self.left = nil
		self.right = nil
	end
end

class MyQueue 
	# Define the accessor and reader of class MyQueue
	attr_reader :head, :tail, :count
	attr_accessor :head, :tail, :count
	def initialize() 
		self.head = nil
		self.tail = nil
		self.count = 0
	end

	def size() 
		return self.count
	end

	def isEmpty() 
		return self.count == 0
	end

	#  Add new node of queue
	def enqueue(value) 
		#  Create a new node
		node = QNode.new(value)
		if (self.head == nil) 
			#  Add first element into queue
			self.head = node
		else
 
			#  Add node at the end using tail
			self.tail.next = node
		end

		self.count += 1
		self.tail = node
	end

	#  Delete a element into queue
	def dequeue() 
		if (self.head == nil) 
			#  Empty Queue
			return
		end

		#  Visit next node
		self.head = self.head.next
		self.count -= 1
		if (self.head == nil) 
			#  When deleting a last node of linked list
			self.tail = nil
		end

	end

	#  Get front node
	def peek() 
		if (self.head == nil) 
			return nil
		end

		return self.head.data
	end
end

class BinaryTree 
	# Define the accessor and reader of class BinaryTree
	attr_reader :root
	attr_accessor :root
	def initialize() 
		self.root = nil
	end

	def levelOrder() 
		if (self.root != nil) 
			q = MyQueue.new()
			#  Add first node
			q.enqueue(self.root)
			node = self.root
			while (q.isEmpty() == false && node != nil) 
				if (node.left != nil) 
					#  Add left child node
					q.enqueue(node.left)
				end

				if (node.right != nil) 
					#  Add right child node
					q.enqueue(node.right)
				end

				#  Display level node
				print("  ", node.data)
				#  Remove current node
				q.dequeue()
				#  Get new head
				node = q.peek()
			end

		else
 
			print("Empty Tree\n")
		end

	end

end

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

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