Morris Inorder Algorithm

The Morris Inorder Algorithm is an innovative tree traversal algorithm designed to perform an inorder traversal of a binary tree without using any additional memory for storage of parent pointers or using a recursive call stack. This algorithm is particularly useful in situations where memory is a constraint, or when an efficient traversal is required. The main idea behind the Morris Inorder Algorithm is to temporarily modify the tree structure by creating links to the inorder predecessor nodes, which allow us to traverse the tree without additional memory usage, and then restore the tree back to its original structure after the traversal is complete. To achieve this, the algorithm starts at the root node and iteratively processes the left and right subtrees. For each visited node, it checks if it has a left child. If a left child exists, the algorithm finds the rightmost node in the left subtree (inorder predecessor), and creates a temporary link from this rightmost node to the current node. This link allows us to move back to the current node after traversing its left subtree. Once the traversal of the left subtree is complete, the temporary link is removed, and the algorithm proceeds to traverse the right subtree. If a visited node does not have a left child, it means that the inorder traversal of its left subtree is complete, and the algorithm directly proceeds to traverse its right subtree. By following this approach, the Morris Inorder Algorithm successfully traverses the binary tree without using any extra memory, making it a highly efficient and memory-friendly solution for tree traversal tasks.
#include <iostream>
#include <queue>

/**************************
	@author shrutisheoran
**************************/

using namespace std;

struct Btree
{
	int data;
	struct Btree *left;  //Pointer to left subtree
	struct Btree *right; //Pointer to right subtree
};

void insert(Btree **root, int d)
{
	Btree *nn = new Btree(); //Creating new node
	nn->data = d;
	nn->left = NULL;
	nn->right = NULL;
	if (*root == NULL)
	{
		*root = nn;
		return;
	}
	else
	{
		queue<Btree *> q;
		// Adding root node to queue
		q.push(*root);
		while (!q.empty())
		{
			Btree *node = q.front();
			// Removing parent node from queue
			q.pop();
			if (node->left)
				// Adding left child of removed node to queue
				q.push(node->left);
			else
			{
				// Adding new node if no left child is present
				node->left = nn;
				return;
			}
			if (node->right)
				// Adding right child of removed node to queue
				q.push(node->right);
			else
			{
				// Adding new node if no right child is present
				node->right = nn;
				return;
			}
		}
	}
}

void morrisInorder(Btree *root)
{
	Btree *curr = root;
	Btree *temp;
	while (curr)
	{
		if (curr->left == NULL)
		{
			cout << curr->data << " ";
			// If left of current node is NULL then curr is shifted to right
			curr = curr->right;
		}
		else
		{
			// Left of current node is stored in temp
			temp = curr->left;
			// Moving to extreme right of temp
			while (temp->right && temp->right != curr)
				temp = temp->right;
			// If extreme right is null it is made to point to currrent node (will be used for backtracking)
			if (temp->right == NULL)
			{
				temp->right = curr;
				// current node is made to point its left subtree
				curr = curr->left;
			}
			// If extreme right already points to currrent node it it set to null
			else if (temp->right == curr)
			{
				cout << curr->data << " ";
				temp->right = NULL;
				// current node is made to point its right subtree
				curr = curr->right;
			}
		}
	}
}

int main()
{
	// Testing morrisInorder funtion
	Btree *root = NULL;
	int i;
	for (i = 1; i <= 7; i++)
		insert(&root, i);
	cout << "Morris Inorder: ";
	morrisInorder(root);
	return 0;
}

LANGUAGE:

DARK MODE: