Reverse spiral traversal of a binary tree in scala
Scala program for Reverse spiral traversal of a binary tree. Here problem description and explanation.
/*
Scala program for
Reverse level order traversal in spiral form
*/
// Binary Tree Node
class TreeNode(var data: Int,
var left: TreeNode,
var right: TreeNode)
{
def this(data: Int)
{
// Set node value
this(data, null, null);
}
}
// Stack node
class StackNode(
// Stack data
var element: TreeNode,
var next: StackNode);
// Define a custom stack
class MyStack(var top: StackNode,
var size: Int)
{
def this()
{
this(null, 0);
}
// Add node at the top of stack
def push(element: TreeNode): Unit = {
this.top = new StackNode(element, this.top);
this.size += 1;
}
def isEmpty(): Boolean = {
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
def pop(): Unit = {
if (this.size > 0 && this.top != null)
{
// Change top element of stack
this.top = this.top.next;
this.size -= 1;
}
}
// Return top element of stack
def peek(): TreeNode = {
if (this.size == 0)
{
return null;
}
return this.top.element;
}
}
class BinaryTree(var root: TreeNode)
{
def this()
{
this(null)
}
// Display tree element in reverse spiral level order traversal
def reverseSpiral(): Unit = {
if (this.root == null)
{
// Case
// When empty
println("Empty Tree");
return;
}
// Empty stack
var s1: MyStack = new MyStack();
var s2: MyStack = new MyStack();
var result: MyStack = new MyStack();
// Some auxiliary variable
var status: Int = 1;
var node: TreeNode = this.root;
// Add first node
s1.push(node);
while (node != null)
{
// Add node element into resultant stack
result.push(node);
if (status == 1)
{
// Add node from right to left
// in s2 stack
if (node.right != null)
{
// Add right child
s2.push(node.right);
}
if (node.left != null)
{
// Add left child
s2.push(node.left);
}
}
else
{
// Add node from left to right
// in s1 stack
if (node.left != null)
{
// Add left child
s1.push(node.left);
}
if (node.right != null)
{
// Add right child
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
while (result.isEmpty() == false)
{
// Get top element
node = result.peek();
// Display node value
print(" " + node.data);
// Remove top of stack
result.pop();
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
// Create new tree
var tree: BinaryTree = new BinaryTree();
/* Make A Binary Tree
---------------
1
/ \
/ \
2 3
/ / \
4 5 6
\ \ \
7 8 9
*/
// Add node
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.right.right = new TreeNode(6);
tree.root.right.left = new TreeNode(5);
tree.root.left.left = new TreeNode(4);
tree.root.left.left.right = new TreeNode(7);
tree.root.right.left.right = new TreeNode(8);
tree.root.right.right.right = new TreeNode(9);
// Display reverse spiral level order element
tree.reverseSpiral();
}
}
Output
9 8 7 4 5 6 3 2 1
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