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

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_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
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)
s2.push(node.right)
end

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

else

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

if (node.right != nil)
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
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.

Categories
Relative Post