A tree is not a linear structure and hence, can be traversed in many ways. To traverse a tree, we need to go through all its nodes in some order, which can be — inorder, preorder, or postorder depth-first traversal and level order, breadth-first traversal, or some hybrid scheme. In this article, we discuss inorder tree traversal without the use of recursion or stack.
If you are preparing for a tech interview, check out our technical interview checklist, interview questions page, and salary negotiation e-book to get interview-ready! Also, read Python String join() Method, Sum Function in Python, and How to Read and Write Files in Python for more specific insights and guidance on Python concepts and coding interview preparation.
Having trained over 9,000 software engineers, we know what it takes to crack the toughest tech interviews. Since 2014, Interview Kickstart alums have been landing lucrative offers from FAANG and Tier-1 tech companies, with an average salary hike of 49%. The highest ever offer received by an IK alum is a whopping $933,000!
At IK, you get the unique opportunity to learn from expert instructors who are hiring managers and tech leads at Google, Facebook, Apple, and other top Silicon Valley tech companies.
Want to nail your next tech interview? Sign up for our FREE Webinar.
In this article, we’ll discuss:
- What Is Inorder Tree Traversal?
- Inorder Tree Traversal Without Recursion and Stack Example
- Time Complexity
- Advantages and Disadvantages of Inorder Tree Traversal Using Morris Traversal
- Problems and Interview Questions on Inorder Tree Traversal
- FAQs on Inorder Tree Traversal Without Recursion and Stack
What Is Inorder Tree Traversal?
The process of traversing a tree that involves visiting the left child and its entire subtree first, then visiting the node, and lastly, visiting the right child and its entire subtree similarly is called inorder traversal.
This traversal method can be especially useful in the case of binary search trees, where it helps output all the node values in ascending order.
To learn more about other types of tree travels, read Tree Traversal: Inorder, Preorder, Postorder, and Level-order.
Inorder Tree Traversal Without Recursion and Stack Example
Since a tree is not a linear data structure, and nodes can have multiple child nodes, there can be many possible nodes to visit after a node is visited. Nodes that need to be visited later need to, in some manner, be stored for a future visit.
This could be achieved by storing the nodes in a stack for future visits or using recursion, where the nodes are implicitly stored in a stack for future visits. This article, however, is not about these two methods. It’s about how we can do inorder tree traversal without involving recursion or stack using Morris Traversal.
Problem Statement
Achieve inorder tree traversal without using recursion and without using stack.
Solution: Morris Traversal
Morris Traversal is a method based on the idea of a threaded binary tree and can be used to traverse a tree without using recursion or stack. Morris traversal involves:
- Step 1: Creating links to inorder successors
- Step 2: Printing the information using the created links (the tree is altered during the traversal)
- Step 3: Once the traversal has been completed, reverting the changes and restoring the original tree
Note that unlike when we use the stack for traversal, we don’t need any additional space in this method.
Look at the pseudocode, and code below to understand this process better:
Morris Traversal Pseudocode
Initialize the variable “current” node as the root
While the “current” node is not NULL
If the current node lacks a left child
Print the information in the current node
Visit the right child, current = current->right
Else
In the current left subtree, find the rightmost node or find the node whose right child == current.
If the node’s right child == current
Update the node’s right child as NULL
Print the information in current
Visit the right child, current = current->right
Else
Set the current variable as the right child of that rightmost node found; and
Visit the left child, current = current->left
Code for Inorder Traversal Using Morris Traversal
#include <stdio.h>
#include <stdlib.h>
/* Each treeNode holds some value, a pointer to left child (leftChild)
and a pointer to right child (rightChild) */
struct treeNode
{
int value;
struct treeNode* leftChild;
struct treeNode* rightChild;
};
/* A method to traverse a tree using Morris traversal, hence without using recursion or stack */
void MorrisTraversal(struct treeNode* root)
{
struct treeNode *current, *predecessorofCurrent;
if (root == NULL)
return;
current = root;
//The while loop continues till our current root is not NULL
while (current != NULL)
{
if (current->leftChild == NULL)
{
printf("%d ", current->value);
current = current->rightChild;
}
else
{
//Getting the inorder predecessor of the current node
predecessorofCurrent = current->leftChild;
while (predecessorofCurrent->rightChild != NULL
&& predecessorofCurrent->rightChild != current)
predecessorofCurrent = predecessorofCurrent->rightChild;
/* Setting the right child of predecessorofCurrent as current, and update current to the value of the leftChild of the current */
if (predecessorofCurrent->rightChild == NULL)
{
predecessorofCurrent->rightChild = current;
current = current->leftChild;
}
/* Reverting the changes made due to the if block to
restore the tree to its original state by fixing the right
child of the predecessor. Printing the result of traversal */
else
{
predecessorofCurrent->rightChild = NULL;
printf("%d ", current->value);
current = current->rightChild;
}
}
}
}
/* A utility/helper function to allocate a new treeNode with the
given value, along with NULL leftChild and NULL rightChild pointers. */
struct treeNode* newtreeNode(int value)
{
struct treeNode* node = new treeNode;
node->value = value;
node->leftChild = NULL;
node->rightChild = NULL;
return (node);
}
int main()
{
/* The tree created:
4
/ \
2 5
/ \
1 3
*/
struct treeNode* root = newtreeNode(4);
root->leftChild = newtreeNode(2);
root->rightChild = newtreeNode(5);
root->leftChild->leftChild = newtreeNode(1);
root->leftChild->rightChild = newtreeNode(3);
/* Morris Traversal for the created tree */
MorrisTraversal(root);
return 0;
}
Output
1 2 3 4 5
Time Complexity
When it comes to time complexity, we can note the following about Morris traversal:
- The number of times an edge is visited is constant in Morris traversal. For example, for a binary tree, one edge is visited at most thrice:
1) The first visit aims to locate a node
2) The second visit aims to find the predecessor of a node
3) The third visit is for restoring the right child of the predecessor to NULL - Since the number of times the node will be traversed is constant, the time complexity is O(n).
- At worst, a predecessor has to be found for each node. In that case, the number of additional edges created and removed will be equal to the number of edges in the input tree.
Advantages and Disadvantages of Inorder Tree Traversal Using Morris Traversal
Some advantages of using the Morris Traversal method for inorder tree traversal include:
- Allows inorder tree traversal without using recursion and stack
- Does not require additional space, unlike when a stack is used for the purpose.
- Does not require as much memory and time as recursion.
- The node keeps track of its parent.
Some disadvantages of using the Morris Traversal method for inorder tree traversal include:
- Makes for a more complex tree.
- Only one traversal can be done at a time.
- Can be error-prone in cases where both the children are absent from a binary tree, and both values of the nodes point to their ancestors.
Problems and Interview Questions on Inorder Tree Traversal
- Implement inorder tree traversal using stack
- Implement inorder tree traversal using recursion
- Implement inorder tree traversal without using recursion or stack
- What is the Morris Traversal method for inorder traversal? Can you use it for preorder traversal?
- What are some advantages and disadvantages of using Morris Traversal?
FAQs on Inorder Tree Traversal Without Recursion and Stack
1. How do you implement inorder traversal without recursion?
You can implement inorder traversal without using recursion using a stack and using Morris Traversal.
2. Which method of tree traversal does not use a stack?
The recursion method implicitly uses a stack, so out of the three tree traversal methods — stack, recursion, and Morris Traversal — Morris Traversal is the traversal method that does not use a stack.
3. What is a threaded binary tree?
A binary tree in which every node that does not have a right child has a link (or thread) to its inorder successor is called a threaded binary tree. This helps us in avoiding the use of recursion during traversal, saving memory and time consumption.
4. How many ways can we use to traverse a tree?
Broadly, we commonly traverse trees using breadth-first or depth-first algorithms. There are sub-parts to both, and there are hybrid ways as well. But commonly, breadth- and depth-first are the two broad categories used most often for tree traversal.
5. In how many ways can we traverse a tree in depth-first order?
There are three ways to traverse a tree in depth-first order: Inorder, Preorder, and Postorder.
Ready to Nail Your Next Coding Interview?
Whether you’re a Coding Engineer gunning for Software Developer or Software Engineer roles, a Tech Lead, or you’re targeting management positions at top companies, IK offers courses specifically designed for your needs to help you with your technical interview preparation!
If you’re looking for guidance and help with getting started, sign up for our FREE webinar. As pioneers in the field of technical interview preparation, we have trained thousands of software engineers to crack the toughest coding interviews and land jobs at their dream companies, such as Google, Facebook, Apple, Netflix, Amazon, and more!
.png)
