# Reverse spiral traversal of a binary tree in golang

Go program for Reverse spiral traversal of a binary tree. Here problem description and other solutions.

``````package main
import "fmt"
/*
Go program for
Reverse level order traversal in spiral form
*/
// Binary Tree Node
type TreeNode struct {
data int
left * TreeNode
right * TreeNode
}
func getTreeNode(data int) * TreeNode {
// return new TreeNode
return &TreeNode {
data,
nil,
nil,
}
}
// Stack node
type StackNode struct {
// Stack data
element * TreeNode
next * StackNode
}
func getStackNode(element * TreeNode,
top * StackNode) * StackNode {
// return new StackNode
return &StackNode {
element,
top,
}
}
// Define a custom stack
type MyStack struct {
top * StackNode
size int
}
func getMyStack() * MyStack {
// return new MyStack
return &MyStack {
nil,
0,
}
}
// Add node at the top of stack
func(this *MyStack) push(element * TreeNode) {
this.top = getStackNode(element, this.top)
this.size++
}
func(this MyStack) isEmpty() bool {
if this.size > 0 && this.top != nil {
return false
} else {
return true
}
}
// Remove top element of stack
func(this *MyStack) pop() {
if this.size > 0 && this.top != nil {
// Change top element of stack
this.top = this.top.next
this.size--
}
}
func(this MyStack) peek() * TreeNode {
if this.size == 0 {
return nil
}
return this.top.element
}
type BinaryTree struct {
root * TreeNode
}
func getBinaryTree() * BinaryTree {
// return new BinaryTree
return &BinaryTree {
nil,
}
}
// Display tree element in reverse spiral level order traversal
func(this BinaryTree) reverseSpiral() {
if this.root == nil {
// Case
// When empty
fmt.Println("Empty Tree")
return
}
// Empty stack
var s1 * MyStack = getMyStack()
var s2 * MyStack = getMyStack()
var result * MyStack = getMyStack()
// Some auxiliary variable
var status int = 1
var node * TreeNode = this.root
s1.push(node)
for (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)
}
if node.left != nil {
s2.push(node.left)
}
} else {
// Add node from left to right
// in s1 stack
if node.left != nil {
s1.push(node.left)
}
if node.right != nil {
s1.push(node.right)
}
}
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()
}
} 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()
}
}
}
// Display final result
for (result.isEmpty() == false) {
// Get top element
node = result.peek()
// Display node value
fmt.Print("   ", node.data)
// Remove top of stack
result.pop()
}
}
func main() {
// Create new tree
var tree * BinaryTree = getBinaryTree()
/*   Make A Binary Tree
---------------
1
/ \
/   \
2     3
/     / \
4     5   6
\    \    \
7    8    9

*/
tree.root = getTreeNode(1)
tree.root.left = getTreeNode(2)
tree.root.right = getTreeNode(3)
tree.root.right.right = getTreeNode(6)
tree.root.right.left = getTreeNode(5)
tree.root.left.left = getTreeNode(4)
tree.root.left.left.right = getTreeNode(7)
tree.root.right.left.right = getTreeNode(8)
tree.root.right.right.right = getTreeNode(9)
// Display reverse spiral level order element
tree.reverseSpiral()
}``````

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.