Do you think IIT Guwahati certified course can help you in your career?
Introduction
Traversing in data structures is an important aspect when dealing with different data structures. If we talk about tree traversal, then as the name suggests, it is the process of visiting all the nodes of a tree in a specific order.
You must have heard about In Order, Preorder, Postorder and Level Order Traversal. But in this article, we will be talking about one lesser known but elegant method for traversing binary trees, i.,e, Morris Traversal Algorithm.
We will deep dive into the Intuition being designing such algorithms. We will also see its complexity analysis followed by the frequently asked questions.
So, let us start our journey:
Understanding Tree Traversal
Trees in Computer Science are data structures consisting of nodes, with each node potentially having one or more child nodes. Traversing a tree means visiting all of the nodes in a specific order.
There are mainly three types of tree traversals:
Inorder Traversal: Visits nodes in ascending order for a binary search tree (BST). In other words, it visits the left subtree, then the current node, and finally the right subtree.
Preorder Traversal: Visits the current node before its child nodes. It starts from the root node and moves towards the leaves.
Postorder Traversal: Visits the current node after its child nodes. It starts from the leaves and moves towards the root.
Now, you must be wondering, when we have these traversals, why do we worry about the other one: Morris traversal.
The answer to this question is because of the space/memory issue of these algos. All these algos often use recursion or stack to keep track of the nodes and their order of visitation. While these methods work well, they require additional memory space for maintaining the call stack or an explicit stack data structure. The Morris Traversal Algorithm aims to perform tree traversal without any extra memory usage, making it highly efficient in terms of space.
Need of the Morris Traversal
Let us go through the Inorder Traversal once then we will compare the tradition Inorder traversal with the Morris Traversal.
Let us take an example of a binary Tree:
If we try to traverse the tree in an Inorder fashion, then we will start with the left most node, followed by the root node and then the right node. This follows until we visit all the nodes as you can see in the below image.
To implement the above idea, we will need to go back which requires some sort of additional data structure like a stack for Iterative approach. This results in a high memory consumption which is not an optimal solution. We can also use Recursion which again internally follows the same idea.
So, to overcome this, we need some sort of algorithm that reduces the space complexity while maintaining the performance as it is.
Here, comes the Morris Traversal which is designed to resolve this issue.
Now that you have understood the Intuition behind the Morris Traversal, let us quickly jump into its concept architecture.
Understanding the Morris Traversal
The idea behind the Morris Traversal is to create the temporary links between the nodes so that we have a way to come back. We are calling them temporary links as we are going to remove them once the traversal is done.
Algorithm
Here's how the Morris Traversal Algorithm works for an inorder traversal:
Start at the root node.
While the current node is not null:
If the current node has no left child:
=> visit the current Node
=> make the right child as the current Node.
Else:
Find the rightmost (maximum) node in the left subtree (this is the predecessor of the current node). We find the predecessor of the current by moving one step towards the left and then the rightmost node from the left. The rightmost node will be the predecessor of the current node.
If predecessor.right doesnot exist, Make the predecessor.right = current. This will generate the temporary link between the current and the predecessor node. Next, make the current = current.left
Else: do the predecessor.right = Null Visit the current Node Make the current = current.right.
Pseudo Code
current = root
while current is not NULL:
if not exists current.left:
visit(current)
current = current.right
else
predecessor = findPredecessor(current)
if not exists predecessor.right
predecessor.right = current
current = current.left
else
predecessor.right = Null
visit(current)
current = current.right
Let us see one example to look at its working.
Step 1: Start with the Root Node, i.,e, make it the current Node.
Step 2: The next step is to find whether the current.left exists or not. In our case, it does exist. The next move is to find the predecessor of the current node, i.,e, 10.
Step 3: If predecessor.right doesnot exist, Make the predecessor.right = current. Now we will make the temporary link between the predecessor and the current node.
Step 4: The next move is to update the current. Now current will become current.left.
Step 5: This step contains again checking the previous conditions. We will check if our current has current.left or not. It does exist, we will quickly find its predecessor.
In this case, the right node doesn’t exist, so the predecessor will be 2 itself. Now, again we will generate the link between 2 and the 5(current node at the moment).
Step 6: The next step is again updating the current node to its current.left.
Step 7: Now comes the interesting part, we don’t have now current.left so we will now visit the current node ( 2) and update the current node again by its current.right. So, the current.right is 5. It is due to the link we have created just now.
Step 8: At this moment, the current node is 5 which again has a current.left. So, we will again find the predecessor of the current node. In this case, predecessor.right does exist. That means, we have already covered this cycle.
So, we will follow these rules:
Else: do the predecessor.right = Null
Visit the current Node
Make the current = current.right.
We will break the link and visit the current node and update the current node as current.right. In our case, the current node will now become 7.
The same steps will be followed until the current node becomes null. The final result will be the Inorder traversal of the binary tree.
Let us now see its Implementation in different languages:
C++
Java
C++
#include <iostream>
// Definition for a binary tree node. struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };
void morrisInorderTraversal(TreeNode* root) { TreeNode* current = root;
while (current != nullptr) { if (current->left == nullptr) { // If the current node has no left child, visit it and move to the right. std::cout << current->val << " "; current = current->right; } else { // Find the rightmost node in the left subtree (predecessor). TreeNode* predecessor = current->left; while (predecessor->right != nullptr && predecessor->right != current) { predecessor = predecessor->right; }
if (predecessor->right == nullptr) { // Make the current node the right child of its predecessor. predecessor->right = current; current = current->left; } else { // Revert the change made in the previous step. predecessor->right = nullptr; std::cout << current->val << " "; // Visit the current node. current = current->right; } } } }
int main() { // Create a sample binary tree. TreeNode* root = new TreeNode(10); root->left = new TreeNode(5); root->right = new TreeNode(15); root->left->left = new TreeNode(2); root->left->right = new TreeNode(7); root->right->right = new TreeNode(30);
class TreeNode { int val; TreeNode left; TreeNode right;
public TreeNode(int x) { val = x; left = null; right = null; } }
class morrisInorderTraversal { public static void morrisInorderTraversal(TreeNode root) { TreeNode current = root;
while (current != null) { if (current.left == null) { // If the current node has no left child, visit it and move to the right. System.out.print(current.val + " "); current = current.right; } else { // Find the rightmost node in the left subtree (predecessor). TreeNode predecessor = current.left;
if (predecessor.right == null) { // Make the current node the right child of its predecessor. predecessor.right = current; current = current.left; } else { // Revert the change made in the previous step. predecessor.right = null; System.out.print(current.val + " "); // Visit the current node. current = current.right; } } } }
public static void main(String[] args) { // Create a sample binary tree. TreeNode root = new TreeNode(10); root.left = new TreeNode(5); root.right = new TreeNode(15); root.left.left = new TreeNode(2); root.left.right = new TreeNode(7); root.right.right = new TreeNode(30);
Here is the breakdown of the complexity analysis of Morris Traversal:
Time Complexity:
The time complexity of the Morris Traversal algorithm is O(n), where 'n' is the number of nodes in the binary tree.
This complexity analysis is based on the fact that each node is visited exactly twice: once when establishing the Morris links (in the worst case) and once when traversing the tree.
Space Complexity:
The Morris Traversal algorithm is renowned for its space efficiency because it uses only a constant amount of extra space, making it an in-place traversal method.
The space complexity is O(1), indicating that the amount of memory used by the algorithm is not dependent on the size of the input tree.
Frequently Asked Questions
What is traversing in data structure?
Traversing in data structure means iterating over each data structure element systematically to access them.
What are the names of techniques for traversing a tree?
The four main techniques for traversing a tree are level order, inorder, preorder, and postorder traversal.
What is the difference between traversing and searching?
In traversing, we are iterating over all the elements in the data structure at least once. In searching, we iterate through the data structure to find the particular element(s).
Conclusion
The Morris Traversal Algorithm is a clever and memory-efficient way to traverse binary trees. It uses the tree's own structure to achieve efficient traversal without additional memory overhead. While it may not be as widely known as other traversal techniques, understanding this algorithm can be valuable for situations where memory is limited or when you want to perform in-order tree traversal efficiently.
We have more for you. Give a read to the following articles to learn more about Traversals:
24+ registered 
