Posted on by Kalkicode
Code Binary Tree

Morris preorder traversal in scala

Scala program for Morris preorder traversal. Here problem description and other solutions.

/* 
  Scala program for
  Morris traversal preorder
*/
// Binary Tree Node
class TreeNode(var data: Int,
	var left: TreeNode,
		var right: TreeNode)
{
	def this(data: Int)
	{
		// Set node value
		this(data, null, null);
	}
}
class BinaryTree(var root: TreeNode)
{
	def this()
	{
		this(null);
	}
	//  Recursive function
	// Display preorder view of binary tree
	def preorder(node: TreeNode): Unit = {
		if (node != null)
		{
			// Print node value
			print("  " + node.data);
			preorder(node.left);
			preorder(node.right);
		}
	}
	// iterative preorder tree traversal
	def morrisPreorder(): Unit = {
		if (this.root == null)
		{
			return;
		}
		var current: TreeNode = this.root;
		var auxiliary: TreeNode = null;
		// iterating tree nodes
		while (current != null)
		{
			if (current.left == null)
			{
				// Print node value
				print("  " + 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
					print("  " + 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;
				}
			}
		}
		print("\n");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		// Create new tree
		var tree: BinaryTree = 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);
		println("\n Recursive Preorder");
		// Display preorder elements
		tree.preorder(tree.root);
		println("\n Morris Preorder");
		tree.morrisPreorder();
	}
}

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