Inorder Traversal is a fundamental concept in computer science, especially pertaining to binary trees. It involves visiting the nodes of a tree in a specific sequence: left subtree, root node, followed by the right subtree. Often, this traversal is implemented using recursion, but iterative methods can be employed as well. This article aims to explain how to implement Inorder Traversal without recursion.

Introduction to Inorder Traversal

Binary trees are made up of nodes, where each node has up to two children. The tree is a recursive data structure, which often encourages recursive algorithms to navigate it. Inorder Traversal is one of the methods to traverse a binary tree and is defined by the sequence:

1. Visit the left subtree.
2. Visit the root node.
3. Visit the right subtree.

For a binary search tree (BST), Inorder Traversal yields nodes in non-decreasing order, making it very useful for operations like sorting and printing nodes in a sorted fashion.

Iterative Approach using Stack

To perform Inorder Traversal iteratively, a stack is utilized to maintain the track of nodes. The main idea is to simulate the call stack that recursion implicitly uses.

Steps

1. Initialize an empty stack.
2. Set current node to root.
3. Iterate while either the stack is not empty or the current node is not null.
   • Push the current node to the stack and set `current` to its left child.
   • If the current node becomes null, pop the node from the stack, visit it (process the root node), and set `current` to its right child.

Example

Consider the binary tree:

2 5 1 3

• Space Complexity: Both recursive and iterative approaches have a space complexity of $O(h)$, where $h$ is the height of the tree. The iterative method provides control over the stack size and can prevent stack overflow errors in case of very deep recursion.
• Non-Recursive Benefits: Iterative methods are often favored where deep recursion can lead to stack overflow or when explicit stack control is required.