Traversing data structures is indeed one of the core and fundamental operations in computer science and programming. It's a fundamental building block for many algorithms and is essential for various tasks and applications.. When 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 Preorder Algorithm.

So, let us start our journey:

Understanding Tree Traversal

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.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Need of the Morris Traversal Preorder

So far we have discussed the traversals that are Iterative or Recursive. In the Iterative approach, we used Stack and in the recursive approach, the stack is implemented internally for maintaining the calls.

While these approaches 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. So, we aim to achieve O(1) space complexity with the help of Morris Traversal Algorithm.

Understanding the Morris Traversal Preorder

Morris Traversal Preorder is a variation of the Morris Traversal algorithm that allows you to traverse a binary tree in preorder (root-left-right) order without using additional memory structures like stacks. It uses the Morris Link technique to achieve this. The links which we will be generating between the nodes will be temporary, that means after successful traversal of the nodes, the changes are reverted back to restore the original tree.

Algorithm

Here's how the Morris Traversal Algorithm works for an Preorder traversal:

1. Start at the root node.
2. While the current node is not null:
2.1 If the current node has no left child:
2.1.1 Visit the current Node
Make the right child as the current Node.
2.2 Else:
Find the rightmost (maximum) node in the left subtree (this is the predecessor of the current node).
2.2.1 If predecessor.right does not exist,
Make the predecessor.right = current. This will generate the temporary link between the current and the predecessor node.
Visit the current Node
Next, make the current = current.left
2.2.2 Else:
Do the predecessor.right = Null ( Remove the temporary link )
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
visit(current)
current = current.left
else
predecessor.right = Null
current = current.right

Time for an Example

Let us see one example to look at its working.

We have the following binary tree:

Let us quickly find its preorder:

The Preorder will be : 10 5 2 7 15 30

Let us try to find the same result using the Morris Traversal algorithm:

Step 1: Make the root as the current node.

Step 2: Check if the current.left exists or not. In our case it does exist, so we will find the predecessor to the current Node(10). Make the predecessor.right = current.

Step 3: The next step is to visit the Current Node (10).

Step 4: Update the Current to Current.left.

So far, one iteration is done. Let us move to the second iteration, as our Current is not null.

Step 5: Again, we will check if Current.left exists or not. It again exists as you can see in the above diagram. Thus, we will find the predecessor again and will generate the temporary link to the current node.

Step 6: The next is to visit the current node ( 5 ).

Step 7: In this step, we will be updating the Current node to its current.left.

Now, we will move towards the third Iteration.

Step 8: At this point, the current.left doesnâ€™t exist anymore. Now, we will have to perform these rules: visit(current) and update the current with current.right.

In the above image, you can see we have utilized the temporary link to update the current with the current.right.

4th Iteration:

Step 9: This is the interesting part. Now, at this point, the current.left does exist. So, we will find the predecessor. The predecessor will be 2. Now, if you check the condition: If predecessor.right doesn't exist then visit the current node. But, in this case, predecessor.right does exist.

So, now we will be doing these operations:

Do the predecessor.right = Null ( Remove the temporary link )

Make the current = current.right.

Step 10: Remove the temporary link and update the current node with its current.right.

The same steps will be followed until the current node becomes null. The final result will be the Preorder traversal of the binary tree.

// 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;

std::cout << current->val << " "; // Visit the current node.

current = current->left;

} else {

// Revert the change made in the previous step.

predecessor->right = nullptr;

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);

std::cout << "Morris Preorder Traversal: ";

morrisPreorderTraversal(root);

return 0;

}

Java

class TreeNode { int val; TreeNode left; TreeNode right;

public TreeNode(int x) { val = x; left = null; right = null; } }

class MorrisPreorderTraversal { public static void morrisPreorderTraversal(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; System.out.print(current.val + " "); // Visit the current node. current = current.left; } else { // Revert the change made in the previous step. predecessor.right = null; 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 the major difference between Morris Inorder Traversal and Morris Preorder Traversal?

Morris Inorder Traversal visits nodes in the order of left-root-right, while Morris Preorder Traversal visits nodes in the order of root-left-right. The primary difference is the timing of when the current node is visited (in the leftward move for Morris Inorder and during the initial step for Morris Preorder).

Is Morris Preorder Traversal commonly used in practice?

While Morris Traversal techniques are elegant and memory-efficient, they are less commonly used in practice compared to traditional recursive or stack-based approaches. This is because they involve modifying the tree temporarily, which may not be desirable in certain scenarios.

Are there any limitations to Morris Preorder Traversal?

Morris Traversal techniques are not well-suited for multithreaded environments or concurrent access to the tree structure, as they involve modifying the tree. Additionally, they may be less intuitive and harder to debug compared to traditional traversal methods.

Conclusion

To summarise the discussion, we have extensively discussed the Morris Traversal Preorder. We have started with discussing the types of traversals followed by the need of the Morris Traversal. As we have seen that it eliminates the need of stack in the algorithm which is an elegant approach and undoubtedly memory efficient. Yet, this amazing algorithm is lesser known in the market but plays a crucial role in Interviews.

We have more for you. Give a read to the following articles to learn more about Traversals: