Level order traversal using queue in typescript
Ts program for Level order traversal using queue. Here more information.
/*
TypeScript program for
Level order tree traversal using queue
*/
// Create Q node
class QNode
{
public data: TreeNode;
public next: QNode;
constructor(node: TreeNode)
{
this.data = node;
this.next = null;
}
}
// 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;
}
}
class MyQueue
{
public head: QNode;
public tail: QNode;
public count: number;
constructor()
{
this.head = null;
this.tail = null;
this.count = 0;
}
public number size()
{
return this.count;
}
public boolean isEmpty()
{
return this.count == 0;
}
// Add new node of queue
public enqueue(value: TreeNode)
{
// Create a new node
var node = new QNode(value);
if (this.head == null)
{
// Add first element into queue
this.head = node;
}
else
{
// Add node at the end using tail
this.tail.next = node;
}
this.count++;
this.tail = node;
}
// Delete a element into queue
public dequeue()
{
if (this.head == null)
{
// Empty Queue
return;
}
// Visit next node
this.head = this.head.next;
this.count--;
if (this.head == null)
{
// When deleting a last node of linked list
this.tail = null;
}
}
// Get front node
public TreeNode peek()
{
if (this.head == null)
{
return null;
}
return this.head.data;
}
}
class BinaryTree
{
public root: TreeNode;
constructor()
{
// Set initial tree root
this.root = null;
}
public levelOrder()
{
if (this.root != null)
{
var q = new MyQueue();
// Add first node
q.enqueue(this.root);
var node = this.root;
while (q.isEmpty() == false && node != null)
{
if (node.left != null)
{
// Add left child node
q.enqueue(node.left);
}
if (node.right != null)
{
// Add right child node
q.enqueue(node.right);
}
// Display level node
console.log(" " + node.data);
// Remove current node
q.dequeue();
// Get new head
node = q.peek();
}
}
else
{
console.log("Empty Tree");
}
}
public static main(args: string[])
{
// Create new tree
var tree = new BinaryTree();
/*
Make A Binary Tree
-----------------------
1
/ \
2 3
/ / \
4 5 6
/ / \
7 8 9
*/
// Adding tree nodes
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.left = new TreeNode(7);
tree.root.right.left.left = new TreeNode(8);
tree.root.right.left.right = new TreeNode(9);
// Display level order element
tree.levelOrder();
}
}
BinaryTree.main([]);
/*
file : code.ts
tsc --target es6 code.ts
node code.js
*/
Output
1
2
3
4
5
6
7
8
9
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