Skip to main content

Morris preorder traversal in swift

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

import Foundation
/* 
  Swift 4 program for
  Morris traversal preorder
*/
// Binary Tree Node
class TreeNode
{
	var data: Int;
	var left: TreeNode? ;
	var right: TreeNode? ;
	init(_ data: Int)
	{
		// Set node value
		self.data = data;
		self.left = nil;
		self.right = nil;
	}
}
class BinaryTree
{
	var root: TreeNode? ;
	init()
	{
		self.root = nil;
	}
	//  Recursive function
	// Display preorder view of binary tree
	func preorder(_ node: TreeNode? )
	{
		if (node  != nil)
		{
			// Print node value
			print(node!.data, terminator: "  ");
			self.preorder(node!.left);
			self.preorder(node!.right);
		}
	}
	// iterative preorder tree traversal
	func morrisPreorder()
	{
		if (self.root == nil)
		{
			return;
		}
		var current: TreeNode? = self.root;
		var auxiliary: TreeNode? = nil;
		// iterating tree nodes
		while (current  != nil)
		{
			if (current!.left == nil)
			{
				// Print node value
				print(current!.data, terminator: "  ");
				// Visit to right childs
				current = current!.right;
			}
			else
			{
				auxiliary = current!.left;
				// Find rightmost node which is not
				// equal to current node
				while (auxiliary!.right  != nil && 
                       (auxiliary!.right !== current))
				{
					// Visit to right subtree
					auxiliary = auxiliary!.right;
				}
				if ((auxiliary!.right !== current))
				{
					// Print node value
					print(current!.data, terminator: "  ");
					// Connect rightmost right node to current node
					auxiliary!.right = current;
					// Visit to left childs
					current = current!.left;
				}
				else
				{
					// unlink
					auxiliary!.right = nil;
					// Visit to right child
					current = current!.right;
				}
			}
		}
		print("\n", terminator: "");
	}
	static func main(_ args: [String])
	{
		// Create new tree
		let tree: BinaryTree? = BinaryTree();
		/*
		Create Binary Tree
		         4
		       /   \
		      8     10
		     / \   /  \
		    1   6 7   -3
		       /
		      9
		*/
		// Add tree node
		tree!.root = TreeNode(4);
		tree!.root!.left = TreeNode(8);
		tree!.root!.left!.left = TreeNode(1);
		tree!.root!.right = TreeNode(10);
		tree!.root!.right!.right = TreeNode(-3);
		tree!.root!.right!.left = TreeNode(7);
		tree!.root!.left!.right = TreeNode(6);
		tree!.root!.left!.right!.left = TreeNode(9);
		print("\n Recursive Preorder");
		// Display preorder elements
		tree!.preorder(tree!.root);
		print("\n Morris Preorder");
		tree!.morrisPreorder();
	}
}
BinaryTree.main([String]());

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