Reverse spiral traversal of a binary tree in typescript
Ts program for Reverse spiral traversal of a binary tree. Here more information.
/*
TypeScript program for
Reverse level order traversal in spiral form
*/
// Binary Tree Node
class TreeNode
{
public data: number;
public left: TreeNode;
public right: TreeNode;
constructor(data: number)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
// Stack node
class StackNode
{
// Stack data
public element: TreeNode;
public next: StackNode;
constructor(element: TreeNode, top: StackNode)
{
this.element = element;
this.next = top;
}
}
// Define a custom stack
class MyStack
{
public top: StackNode;
public size: number;
constructor()
{
// Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
public push(element: TreeNode)
{
this.top = new StackNode(element, this.top);
this.size++;
}
public boolean isEmpty()
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
public pop()
{
if (this.size > 0 && this.top != null)
{
// Change top element of stack
this.top = this.top.next;
this.size--;
}
}
// Return top element of stack
public TreeNode peek()
{
if (this.size == 0)
{
return null;
}
return this.top.element;
}
}
class BinaryTree
{
public root: TreeNode;
constructor()
{
// Set initial tree root
this.root = null;
}
// Display tree element in reverse
// spiral level order traversal
public reverseSpiral()
{
if (this.root == null)
{
// Case
// When empty
console.log("Empty Tree");
return;
}
// Empty stack
var s1 = new MyStack();
var s2 = new MyStack();
var result = new MyStack();
// Some auxiliary variable
var status = 1;
var node = 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
console.log(" " + node.data);
// Remove top of stack
result.pop();
}
}
public static main()
{
// Create new tree
var tree = 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();
}
}
BinaryTree.main();
/*
file : code.ts
tsc --target es6 code.ts
node code.js
*/
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