Morris preorder traversal in typescript
Ts program for Morris preorder traversal. Here more information.
/*
TypeScript program for
Morris traversal preorder
*/
// 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 BinaryTree
{
public root: TreeNode;
constructor()
{
// Set the initial value of root
this.root = null;
}
// Recursive function
// Display preorder view of binary tree
public preorder(node: TreeNode)
{
if (node != null)
{
// Print node value
console.log(" " + node.data);
this.preorder(node.left);
this.preorder(node.right);
}
}
// iterative preorder tree traversal
public morrisPreorder()
{
if (this.root == null)
{
return;
}
var current = this.root;
var auxiliary: TreeNode = null;
// iterating tree nodes
while (current != null)
{
if (current.left == null)
{
// Print node value
console.log(" " + current.data);
// Visit to right childs
current = current.right;
}
else
{
auxiliary = current.left;
// Find rightmost node which is not
// equal to current node
while (auxiliary.right != null && auxiliary.right != current)
{
// Visit to right subtree
auxiliary = auxiliary.right;
}
if (auxiliary.right != current)
{
// Print node value
console.log(" " + current.data);
// Connect rightmost right node to current node
auxiliary.right = current;
// Visit to left childs
current = current.left;
}
else
{
// unlink
auxiliary.right = null;
// Visit to right child
current = current.right;
}
}
}
console.log("\n");
}
public static main(args: string[])
{
// Create new tree
var tree = new BinaryTree();
/*
Create Binary Tree
4
/ \
8 10
/ \ / \
1 6 7 -3
/
9
*/
// Add tree node
tree.root = new TreeNode(4);
tree.root.left = new TreeNode(8);
tree.root.left.left = new TreeNode(1);
tree.root.right = new TreeNode(10);
tree.root.right.right = new TreeNode(-3);
tree.root.right.left = new TreeNode(7);
tree.root.left.right = new TreeNode(6);
tree.root.left.right.left = new TreeNode(9);
console.log("\n Recursive Preorder");
// Display preorder elements
tree.preorder(tree.root);
console.log("\n Morris Preorder");
tree.morrisPreorder();
}
}
BinaryTree.main([]);
/*
file : code.ts
tsc --target es6 code.ts
node code.js
*/
Output
Recursive Preorder
4
8
1
6
9
10
7
-3
Morris Preorder
4
8
1
6
9
10
7
-3
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