How to Perform Inorder, Non-Recursive Traversal of a Binary Tree

Introduction

Tree traversal is a key concept in data structures, involving the systematic visiting of all nodes in a tree. In the case of inorder traversal, the process involves visiting the left child, then the current node, and finally the right child. Although recursion is a common way to implement this, using an iterative (non-recursive) method can be more effective, especially in systems with limited stack memory. In this article, we will discuss Non-Recursive Traversal of a binary tree.

What Is Inorder Traversal?

Inorder traversal is one of the standard ways to navigate a binary tree. The steps involved are:

• First, explore the left subtree
• Next, access the current node
• Finally, explore the right subtree

When applied to a Binary Search Tree (BST), this traversal method results in the values being visited in ascending order.

Why Use an Iterative Method?

While recursion provides a concise way to implement tree traversal, it depends on the system’s call stack. This can lead to stack overflow issues when dealing with very deep or unbalanced trees. An iterative approach, which uses a manually managed stack, avoids this risk and gives developers more explicit control over the execution flow.

Java Implementation

Here’s how you can perform an inorder traversal in Java using an iterative technique. This version uses a Stack to keep track of nodes that need to be revisited, effectively replacing the call stack used in a recursive approach.

public class InorderTraversal {
	
	class TreeNodeStructure {
	    int value;
	    TreeNodeStructure left;
	    TreeNodeStructure right;

	    TreeNodeStructure(int value) {
	        this.value = value;
	        this.left = null;
	        this.right = null;
	    }
	}

    public static void inorderIterative(TreeNodeStructure root) {
        Stack<TreeNodeStructure> stack = new Stack<>();
        TreeNodeStructure currentNode = root;

        while (currentNode != null || !stack.isEmpty()) {
            // Reach the leftmost node of the current node
            while (currentNode != null) {
                stack.push(currentNode);
                currentNode = currentNode.left;
            }

            // Current must be null at this point
            currentNode = stack.pop();
            System.out.print(currentNode.value + " ");
            
            // Visit the right subtree
            currentNode = currentNode.right;
        }
    }

    public static void main(String[] args) {
        /*
            Constructing the following binary tree:
                    4
                   / \
                  2   5
                 / \
                1   3
        */
        TreeNodeStructure root = new InorderTraversal().new TreeNodeStructure(4);
        root.left = new InorderTraversal().new TreeNodeStructure(2);
        root.right = new InorderTraversal().new TreeNodeStructure(5);
        root.left.left = new InorderTraversal().new TreeNodeStructure(1);
        root.left.right = new InorderTraversal().new TreeNodeStructure(3);

        System.out.println("Inorder traversal (non-recursive):");
        inorderIterative(root);
    }
}

Explanation of the Code

The method inorderIterative begins by initializing a stack and setting the current node to the root. It then enters a loop that continues as long as there are unvisited nodes. The inner loop descends to the leftmost node, pushing each node onto the stack along the way. Once there are no more left children, it processes the top node on the stack (visiting it), then shifts to the right child of the visited node. This process repeats until all nodes have been visited.

Conclusion

Inorder traversal is essential for many tree-related operations, and understanding how to implement it iteratively is valuable for writing efficient, stack-safe Java applications. The non-recursive approach outlined above provides a reliable and controllable method for tree traversal that avoids the limitations of recursion.

You can find the example code on Github.