Posted on by Kalkicode
Code Binary Tree

Reverse spiral traversal of a binary tree in ruby

Ruby program for Reverse spiral traversal of a binary tree. Here problem description and explanation.

#  Ruby program for
#  Reverse level order traversal in spiral form

#  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

#  Stack node
class StackNode 
	# Define the accessor and reader of class StackNode
	attr_reader :element, :next
	attr_accessor :element, :next
	#  Stack data
	def initialize(element, top) 
		self.element = element
		self.next = top
	end
end

#  Define a custom stack
class MyStack 
	# Define the accessor and reader of class MyStack
	attr_reader :top, :size
	attr_accessor :top, :size
	def initialize() 
		self.top = nil
		self.size = 0
	end

	#  Add node at the top of stack
	def push(element) 
		self.top = StackNode.new(element, self.top)
		self.size += 1
	end

	def isEmpty() 
		if (self.size > 0 && self.top != nil) 
			return false
		else
			return true
		end
	end

	#  Remove top element of stack
	def pop() 
		if (self.size > 0 && self.top != nil) 
			#  Change top element of stack
			self.top = self.top.next
			self.size -= 1
		end
	end

	#  Return top element of stack
	def peek() 
		if (self.size == 0) 
			return nil
		end
		return self.top.element
	end
end

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

	#  Display tree element in reverse spiral level order traversal
	def reverseSpiral() 
		if (self.root == nil) 
			#  Case
			#  When empty
			print("Empty Tree\n")
			return
		end

		#  Empty stack
		s1 = MyStack.new()
		s2 = MyStack.new()
		result = MyStack.new()
		#  Some auxiliary variable
		status = 1
		node = self.root
		#  Add first node
		s1.push(node)
		while (node != nil) 
			#  Add node element into resultant stack
			result.push(node)
			if (status == 1) 
				#  Add node from right to left
				#  in s2 stack
				if (node.right != nil) 
					#  Add right child
					s2.push(node.right)
				end

				if (node.left != nil) 
					#  Add left child
					s2.push(node.left)
				end

			else
 
				#  Add node from left to right
				#  in s1 stack
				if (node.left != nil) 
					#  Add left child
					s1.push(node.left)
				end

				if (node.right != nil) 
					#  Add right child
					s1.push(node.right)
				end

			end

			if (status == 1) 
				#  Case A
				#  When execute s1 stack
				#  Remove s1 element
				s1.pop()
				if (s1.isEmpty()) 
					#  When after remove s1 element
					#  s1 stack empty.
					#  Then change stack by s2
					status = 2
					#  Get first element of s2
					node = s2.peek()
				else
 
					#  Otherwise get new top
					node = s1.peek()
				end

			else
 
				#  Case B
				#  When execute s2 stack
				#  Remove s2 element
				s2.pop()
				if (s2.isEmpty()) 
					#  Here change stack
					status = 1
					node = s1.peek()
				else
 
					node = s2.peek()
				end

			end

		end

		#  Display final result
		while (result.isEmpty() == false) 
			#  Get top element
			node = result.peek()
			#  Display node value
			print("   ", node.data)
			#  Remove top of stack
			result.pop()
		end

	end

end

def main() 
	#  Create new tree
	tree = BinaryTree.new()
	#   Make A Binary Tree
	#    ---------------
	#       1
	#      / \ 
	#     /   \
	#    2     3
	#   /     / \
	#  4     5   6
	#   \    \    \
	#    7    8    9
	#  Add node
	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.right = TreeNode.new(7)
	tree.root.right.left.right = TreeNode.new(8)
	tree.root.right.right.right = TreeNode.new(9)
	#  Display reverse spiral level order element
	tree.reverseSpiral()
end

main()

Output

   9   8   7   4   5   6   3   2   1

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