A threaded binary tree is just like a normal binary tree, but they have a specialty in which all the nodes whose right child pointers are NULL point to their in-order successor, and all the nodes whose left child pointers are NULL point to their in-order predecessor. It helps in facilitating faster tree traversal without requiring a stack or recursion.
What is Morris traversal?
Morris traversal is an in-order tree traversal algorithm for binary trees that uses threading. It allows in-order traversal of a binary tree without using recursion or an explicit stack, reducing the space complexity to O(1). Morris traversal modifies the tree temporarily by threading some of its nodes, making it a space-efficient alternative for in-order traversal.
What is Morris Traversal for Inorder?
Morris Traversal is a space-efficient algorithm for traversing binary trees in Inorder without using Recursion or a stack. It modifies the tree structure by adding temporary links between nodes to traverse the tree in a specific order. This approach reduces the space complexity to O(1) but increases the time complexity to O(n^2). It is not commonly used in practice due to its higher time complexity, but it can be useful in certain memory-constrained environments.
Algorithm of Morris traversal for Inorder
The Morris Traversal for Inorder is a type of tree traversal in which we first visit the left subtree then, the root node and in the end, the right subtree, which is the same as Inorder Traversal of the binary tree but without using stack or recursion.
Let us understand it using an example:
Consider the following Binary Tree:
Step 1: Initialize the current node as the root.
Step 2: While the current is not NULL,
- If the current node does not have a left child, print the current node’s value and update it to point to the right, i.e. current = current->right.
- If the current node has a left child, then first connect the rightmost node of the left subtree to the root and then update the current node to point to the left, i.e. current = current-> left.
- Update the right child as NULL of the node whose right child is node current and print the current’s value. Then move to right i.e., current = current->right.
- Make current as of the right child of that rightmost node we found and then go to this left child, i.e., current = current->left.
Step 3: Then, after printing the current node and traversing through it, we remove the threaded link, and the current node is updated to point to the right.
Step 4: After traversing all the nodes of the left subtree and printing the root node, we move to the right subtree by pointing the current node to the right.
Hence, After traversing through the whole binary tree, we have achieved our output.
Let’s have a look at the Implementation of Morris Traversal for Inorder without using recursion and stack.
80 40 100 20 60
Time Complexity: O(n) as there are n number nodes in the binary tree, traversed through each node.
Space Complexity: O(1) as we are not using recursion or a stack.
Morris traversal for Preorder
Morris Traversal for Preorder is a tree traversal algorithm that allows the traversal of a binary tree in pre-order sequence without using recursion or an explicit stack. It modifies the structure of the tree temporarily by creating additional links (threads) to navigate through the tree efficiently.
The basic idea of Morris Preorder Traversal is as follows:
1. Start at the root of the tree.
2. While the current node is not null:
a. Print the value of the current node.
b. If the left child is null, move to the right child.
c. If the left child is not null:
i. Find the rightmost node in the left subtree (the in-order predecessor).
ii. Make the right child of this rightmost node point to the current node.
iii. Move to the left child.
This process is repeated until all nodes in the tree are visited. The algorithm does not require a separate stack, making it an in-place and space-efficient approach for preorder traversal.
Algorithm of Morris traversal for Preorder
Here's a brief overview of the steps involved in Morris Preorder Traversal:
- Initialize the current node as the root.
2. While the current node is not null:
a. If the left child is null:
i. Print the value of the current node.
ii. Move to the right child.
b. If the left child is not null:
i. Find the rightmost node in the left subtree.
ii. If the right child of this rightmost node is null:
- Make it point to the current node.
- Print the value of the current node.
- Move to the left child.
iii. If the right child is already the current node:
- Break the link (set it to null).
- Move to the right child.
This process continues until all nodes are visited in preorder sequence. The Morris Preorder Traversal achieves O(1) space complexity while maintaining a time complexity of O(n), where n is the number of nodes in the binary tree.
Morris Preorder Traversal: 1 2 4 5 3
Time Complexity: O(n) because each node is visited once, and the algorithm doesn't use any additional data structures to store information about the nodes.
Space Complexity: O(1) because the algorithm doesn't use any extra space proportional to the input size. It utilizes the existing structure of the tree and only requires a constant amount of extra space for temporary variables.
Limitations of Morris Traversal:
Morris traversal is a method of traversing a binary tree without using recursion or a stack, which reduces the space complexity to O(1). However, it has some limitations.
Firstly, it modifies the tree structure by creating temporary links, which may not be allowed in certain scenarios. For example, if the binary tree is read-only or shared by multiple threads, Morris traversal may not be suitable.
Secondly, it may not work well with certain types of binary trees, such as skewed trees, where one subtree is much larger than the other. In such cases, Morris traversal may result in an unbalanced traversal, leading to poor performance.
Finally, Morris traversal requires careful handling of edge cases, such as handling the root node and dealing with nodes with only one child. This may add complexity to the implementation and make it harder to debug.
Frequently Asked Questions
What is Morris tree traversal?
We can traverse the tree without using stack or recursion by using Morris Traversal. Morris Traversal is based on the Threaded Binary Tree concept. We build links to Inorder successors and display the data using these links in this traversal, then at the end reverse the changes to restore the original tree.
What is the difference between inorder traversal and Morris inorder traversal?
The main difference between inorder traversal and Morris inorder traversal is that Morris traversal uses constant space without a stack.
What is the time complexity of Morris traversal algorithm?
The time complexity of the Morris traversal algorithm is O(n), where n is the number of nodes in the binary tree.
This article discussed the morris traversal for inorder in the C++ programming language. Morris Traversal uses the concept of Threaded Binary Trees, where the left null pointers are pointed to their inorder predecessors, and the null right pointers are pointed towards their inorder successors using threads. Hence, with the help of this, we got the inorder traversal of a binary tree without using a stack or recursion.
- Level Order Traversal of Binary Tree
- Check if Inorder and Preorder Traversals are Valid Without Building the Tree
- Practise Problems
Recommended problems -
Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.