Skip to main content

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




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.

New Comment