Skip to main content

Inorder traversal of binary tree using stack in ruby

Ruby program for Inorder traversal of binary tree using stack. Here problem description and explanation.

#  Ruby program for
#  Inorder traversal without recursion
#  Using stack

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

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

#  Stack Class
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 new element into stack
	def push(element) 
		#  Create new node
		node = StackNode.new(element)
		node.next = self.top
		#  new node is new top
		self.top = node
		#  Increase the size
		self.size += 1
	end

	#  Remove top element of the stack
	def pop() 
		if (self.top != nil) 
			#  next node is new top
			self.top = self.top.next
			#  Reduce size
			self.size -= 1
		end

	end

	#  Returns the status of empty or non empty stacks
	def isEmpty() 
		if (self.size > 0 && self.top != nil) 
			return false
		else
			return true
		end
	end

	#  Return top element of stack
	def peek() 
		if (self.isEmpty()) 
			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 Inorder view of binary tree
	def inorder() 
		if (self.root != nil) 
			#  Make new stack
			s = MyStack.new()
			node = self.root
			#  Display tree element
			while (!s.isEmpty() || node != nil) 
				if (node != nil) 
					#  Add current node
					s.push(node)
					#  Visit to left subtree
					node = node.left
				else
 
					#  When node is null
					#  Get stack top element
					node = s.peek()
					#  Display node value
					print(" ", node.data)
					#  Remove top element of the stack
					s.pop()
					#  Visit to left subtree of current node
					node = node.right
				end

			end

		else
 
			print("Empty Linked List\n")
		end

	end

end

def main() 
	#  Create new tree
	tree = BinaryTree.new()
	#    Construct Binary Tree
	#    -----------------------
	#        15
	#       /  \
	#      24   54
	#     /    /  \
	#    35   62   13
	#  Add tree nodes
	tree.root = TreeNode.new(15)
	tree.root.left = TreeNode.new(24)
	tree.root.right = TreeNode.new(54)
	tree.root.right.right = TreeNode.new(13)
	tree.root.right.left = TreeNode.new(62)
	tree.root.left.left = TreeNode.new(35)
	#  Display result
	tree.inorder()
end

main()

Output

 35 24 15 62 54 13




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