Inorder traversal without recursion or stack

Inorder traversal without recursion or stack

In last post Threaded binary search tree, we learned what is threaded trees and how to convert a BST to threaded tree. In this post, we will discuss, how can we use threaded BST, how to do inorder traversal without recursion or stack.  Inorder traversal of BST with recursion and stack explains how to do inorder traversal without recursion and using stack.

With threaded binary search tree, right pointer of a node either can be a genuine right child of node or it can be a thread which points to the inorder successor of the node. How can we use this information to traverse a tree?

Inorder traversal without recursion or stack

To traverse a threaded binary search tree, first go to left most node of tree. Why? Because that will be first one to print in inorder traversal. In typical recursion method, we reach to parent by function call return, and in stack based approach, we keep track of parent using stack. In threaded tree, we don’t need to keep track of parent.  At any given node, when there is no right child, it automatically redirects to inorder successor of the node.

Algorithm is something like this:

1. Go to left most node of tree, call it currentNode.
2. While currentNode is not null
   2.1  Print currentNode
   2.2  If currentNode->isThread is true
        2.2.1 Set currentNode = currentNode->right
   2.3  If currentNode->isThread is false
        2.3.1 set currentNode to left most node of currentNode->right.

Inorder traversal without recursion or stack example

Let us understand this algorithm using an example:

inorder traversal without recursion or stack

We will start with root i.e 30 and find left most node, which is 10. CurrentNode = 10. Print 10. Right pointer of 10 is thread, so follow that lead and reach at 15. Print 15.  Right pointer of 15 also is thread, so follow that and reach 20.  Print 20. Now, right pointer of 20 is not thread, so go to right node, i.e 25 and find left most node. which will be 25 itself. Print 25.  25 has right pointer as thread, so move to 30 and print it. At 30, right pointer is not thread, so move to left most pointer of tree rooted at 40. Left most node is 37. Print 37. Right pointer of 37 is thread and follow it and print 40. Right pointer of 40 is not thread, so find left most node of 47( right child of 40 ). which is 47 itself. Print 47 and now, right child is NULL and isThread is also false, so exit the loop.

Hope this walk through help you understand workflow. Let’s see some code

Complexity of inorder traversal without recursion or stack is O(N). There is no extra space required.

There is an argument that there is space requirement when converting BST to threaded BST and also for storing a boolean per node. Answer to that question is BST is converted to threaded tree only once and scanned again and again. Consider a case where multiple processes are scanning tree, if they all use extra space while scanning tree, we may use more memory than one time memory required while conversion. Same argument holds true for an extra boolean, if multiple processes use the same tree, memory used during scan is way more than one time allocated memory.

Please share if there is something wrong or missing. We would love to hear from you. Sharing is caring.