Skip to main content

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





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