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