Posted on by Kalkicode
Code Binary Tree

# 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_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_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_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

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_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)
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

end

end

end

def main()
#  Create new tree
tree = BinaryTree.new()
#    Construct Binary Tree
#    -----------------------
#        15
#       /  \
#      24   54
#     /    /  \
#    35   62   13
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.

Categories
Relative Post