Inorder Tree Traversal without recursion and without stack ?

  • To traverse the tree using Morris Traversal is based on Threaded Binary Tree which means without using stack and recursion. In this traversal, we first create links to Inorder successor and print the data using these links, and finally revert the changes to restore original tree.
    • If current does not have left child
      • Print current’s data
      • Go to the right, i.e., current = current->right
    • Else
      • Make current as right child of the rightmost
      • node in current’s left subtree
      • Go to this left child, i.e., current = current->left
  • When the tree is modified through the traversal, it is reverted back to its original shape after the completion.
  • Unlike Stack based traversal, no extra space is required for this traversal.

Sample Code in C++

#include <stdio.h> 
#include <stdlib.h> 

/* A binary tree tNode has data, pointer to left child 
and a pointer to right child */
struct traversalNode { 
	int data; 
	struct traversalNode* left; 
	struct traversalNode* right; 
}; 

/* Function to traverse binary tree without recursion and 
without stack */
void MorrisTraversal(struct traversalNode* root) 
{ 
	struct traversalNode *current, *pre; 

	if (root == NULL) 
		return; 

	current = root; 
	while (current != NULL) { 

		if (current->left == NULL) { 
			printf("%d ", current->data); 
			current = current->right; 
		} 
		else { 

			/* Find the inorder predecessor of current */
			pre = current->left; 
			while (pre->right != NULL && pre->right != current) 
				pre = pre->right; 

			/* Make current as right child of its inorder 
			predecessor */
			if (pre->right == NULL) { 
				pre->right = current; 
				current = current->left; 
			} 

			/* Revert the changes made in if part to restore 
			the original tree i.e., fix the right child 
			of predecssor */
			else { 
				pre->right = NULL; 
				printf("%d ", current->data); 
				current = current->right; 
			} /* End of if condition pre->right == NULL */
		} /* End of if condition current->left == NULL*/
	} /* End of while */
} 

/* UTILITY FUNCTIONS */
/* Helper function that allocates a new tNode with the 
given data and NULL left and right pointers. */
struct traversalNode* newtraversalNode(int data) 
{ 
	struct traversalNode* node = new traversalNode; 
	node->data = data; 
	node->left = NULL; 
	node->right = NULL; 

	return (node); 
} 

/* Driver program to test above functions*/
int main() 
{ 

	/* Constructed binary tree is 
			12 
		/ \ 
		13	 14 
	/ \ 
	15	 16 
*/
	struct traversalNode* root = newtraversalNode(12); 
	root->left = newtraversalNode(13); 
	root->right = newtraversalNode(14); 
	root->left->left = newtraversalNode(15); 
	root->left->right = newtraversalNode(16); 

	MorrisTraversal(root); 

	return 0; 
}

Output

15 13 16 12 14
  • Time Complexity : O(n) If we investigate, we can see that each edge of the tree is crossed at-most multiple times.
  • Also, in most pessimistic scenario same number of additional edges (as info tree) are made and evacuated.

Categorized in:

Data Structure

Tagged in:

, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,