Inorder traversal of binary tree using stack in typescript
Ts program for Inorder traversal of binary tree using stack. Here problem description and explanation.
// TypeScript program for
// Inorder traversal without recursion
// Using stack
// Binary Tree node
class TreeNode
{
public data: number;
public left: TreeNode;
public right: TreeNode;
// Make a tree node
constructor(data: number)
{
// Set node data
this.data = data;
this.left = null;
this.right = null;
}
}
class StackNode
{
public element: TreeNode;
public next: StackNode;
constructor(element: TreeNode)
{
this.element = element;
this.next = null;
}
}
// Stack Class
class MyStack
{
public top: StackNode;
public size: number;
constructor()
{
this.top = null;
this.size = 0;
}
// Add new element into stack
public push(element: TreeNode)
{
// 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
public 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
public boolean isEmpty()
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Return top element of stack
public TreeNode peek()
{
if (this.isEmpty())
{
return null;
}
return this.top.element;
}
}
class BinaryTree
{
public root: TreeNode;
constructor()
{
// Set initial tree root to null
this.root = null;
}
// Display Inorder view of binary tree
public 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
console.log(" " + node.data);
// Remove top element of the stack
s.pop();
// Visit to left subtree of current node
node = node.right;
}
}
}
else
{
console.log("Empty Linked List\n");
}
}
public static main(args: string[])
{
// 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();
}
}
BinaryTree.main([]);
/*
file : code.ts
tsc --target es6 code.ts
node code.js
*/
Output
35
24
15
62
54
13
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