Skip to main content

Inorder traversal of binary tree using stack in node js

Js program for Inorder traversal of binary tree using stack. Here problem description and explanation.

// Node JS program for
// Inorder traversal without recursion
// Using stack

// Binary Tree node
class TreeNode
{
	// Make a tree node
	constructor(data)
	{
		// Set node data
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class StackNode
{
	constructor(element)
	{
		this.element = element;
		this.next = null;
	}
}
// Stack Class
class MyStack
{
	constructor()
	{
		this.top = null;
		this.size = 0;
	}
	// Add new element into stack
	push(element)
	{
		// Create new node
		var node = new StackNode(element);
		node.next = this.top;
		// new node is new top
		this.top = node;
		// Increase the size
		this.size += 1;
	}
	// Remove top element of the stack
	pop()
	{
		if (this.top != null)
		{
			// next node is new top
			this.top = this.top.next;
			// Reduce size
			this.size -= 1;
		}
	}
	// Returns the status of empty or non empty stacks
	isEmpty()
	{
		if (this.size > 0 && this.top != null)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	// Return top element of stack
	peek()
	{
		if (this.isEmpty())
		{
			return null;
		}
		return this.top.element;
	}
}
class BinaryTree
{
	constructor()
	{
		this.root = null;
	}
	// Display Inorder view of binary tree
	inorder()
	{
		if (this.root != null)
		{
			// Make new stack
			var s = new MyStack();
			var node = this.root;
			// Display tree element
			while (!s.isEmpty() || node != null)
			{
				if (node != null)
				{
					// Add current node
					s.push(node);
					// Visit to left subtree
					node = node.left;
				}
				else
				{
					// When node is null
					// Get stack top element
					node = s.peek();
					// Display node value
					process.stdout.write(" " + node.data);
					// Remove top element of the stack
					s.pop();
					// Visit to left subtree of current node
					node = node.right;
				}
			}
		}
		else
		{
			process.stdout.write("Empty Linked List\n");
		}
	}
}

function main()
{
	// Create new tree
	var tree = new BinaryTree();
	/*
	    Construct Binary Tree
	    -----------------------
	        15
	       /  \
	      24   54
	     /    /  \
	    35   62   13
	*/
	// Add tree nodes
	tree.root = new TreeNode(15);
	tree.root.left = new TreeNode(24);
	tree.root.right = new TreeNode(54);
	tree.root.right.right = new TreeNode(13);
	tree.root.right.left = new TreeNode(62);
	tree.root.left.left = new TreeNode(35);
	// Display result
	tree.inorder();
}
// Start program execution
main();

Output

 35 24 15 62 54 13




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