Posted on by Kalkicode
Code Stack

Iterative postorder traversal using one stack in node js

Js program for Iterative postorder traversal using one stack. Here problem description and other solutions.

/* 
    Node JS program for 
    Iterative postorder traversal using stack
*/
//Binary Tree node
class TreeNode
{
	// Make a new node
	constructor(data)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
// Stack Node
class StackNode
{
	constructor(node, top)
	{
		this.node = node;
		this.next = top;
		this.visit = 0;
	}
}
class MyStack
{
	constructor()
	{
		this.top = null;
		this.count = 0;
	}
	// Returns the number of element in stack
	size()
	{
		return this.count;
	}
	isEmpty()
	{
		if (this.size() > 0)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	// Add a new element in stack
	push(node)
	{
		// Make a new stack node
		// And set as top
		this.top = new StackNode(node, this.top);
		// Increase node value
		this.count++;
	}
	// Remove a top element in stack
	pop()
	{
		if (this.isEmpty() == false)
		{
			this.top = this.top.next;
			// Reduce the size
			this.count--;
		}
	}
	// Used to get top element of stack
	peek()
	{
		if (!this.isEmpty())
		{
			return this.top.node;
		}
		else
		{
			return null;
		}
	}
}
class BinaryTree
{
	constructor()
	{
		this.root = null;
	}
	// Display tree element post Order form
	recursivePostorder(node)
	{
		if (node != null)
		{
			this.recursivePostorder(node.left);
			this.recursivePostorder(node.right);
			// Print node value
			process.stdout.write("  " + node.data);
		}
	}
	iterativePostorder()
	{
		// Get top root of tree
		var node = this.root;
		if (node != null)
		{
			var s = new MyStack();
			// Add first node of stack
			s.push(node);
			while (s.isEmpty() == false)
			{
				s.top.visit += 1;
				if (s.top.visit == 1)
				{
					// When visit to left child
					node = node.left;
				}
				else if (s.top.visit == 2)
				{
					// Visit to right child
					node = node.right;
				}
				else
				{
					// Display node value
					process.stdout.write("  " + s.peek().data);
					// Remove stack element
					s.pop();
					node = null;
				}
				if (node != null)
				{
					// Add new stack element
					s.push(node);
				}
				if (s.top != null)
				{
					node = s.peek();
				}
				else
				{
					node = null;
				}
			}
		}
		else
		{
			console.log("Empty Binary Tree");
		}
	}
}

function main()
{
	// Create new tree
	var tree = new BinaryTree();
	/*
	  Make A Binary Tree
	  ---------------------
	       10
	     /    \
	    2      5
	   / \    /  \
	  1   3  7    2
	     /    \      
	    9       8
	*/
	// Add tree nodes
	tree.root = new TreeNode(10);
	tree.root.left = new TreeNode(2);
	tree.root.right = new TreeNode(5);
	tree.root.right.right = new TreeNode(2);
	tree.root.right.left = new TreeNode(7);
	tree.root.right.left.right = new TreeNode(8);
	tree.root.left.left = new TreeNode(1);
	tree.root.left.right = new TreeNode(3);
	tree.root.left.right.left = new TreeNode(9);
	// Recursive result
	console.log("Recursive Postorder");
	tree.recursivePostorder(tree.root);
	// Iterative result
	console.log("\nIterative Postorder");
	tree.iterativePostorder();
}
// Start program execution
main();

Output

Recursive Postorder
  1  9  3  2  8  7  2  5  10
Iterative Postorder
  1  9  3  2  8  7  2  5  10

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