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.1 Set currentNode = currentNode->right
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: