Search⌘ K
Home
Courses
Programming Discrete Math Concepts for Beginners

Inorder Traversal

Explore iterative and recursive inorder tree traversal in binary trees. Understand how the traversal visits nodes in ascending order and the importance of base cases in recursive algorithms. This lesson helps you implement and compare traversal techniques for effective tree processing.

We'll cover the following...

Iterative inorder tree traversal

Inorder tree traversal is very useful and quickly finds the tree’s balance. When we use inorder tree traversal, we start by recursively visiting the left subtree first. After that, we visit the root and then the right subtree. Each node stores a value, and we know this value as the key. In inorder tree traversal, the output produces sorted key values in ascending order.

First, let’s look at inorder tree traversal using iteration.

Java
import java.util.Stack;
class InOrderBinaryTreeNotRecursive {
    static class TreeNodeClass {
        String data;
        InOrderBinaryTreeNotRecursive.TreeNodeClass left, right;
        TreeNodeClass(String value) {
            this.data = value;
            left = right = null;
        }
        boolean isLeaf() {
            return left == null ? right == null : false;
        }
    }
    // root of the binary tree from where we start our journey
    InOrderBinaryTreeNotRecursive.TreeNodeClass root;
    public void inOrderWithoutRecursion(){
        Stack<InOrderBinaryTreeNotRecursive.TreeNodeClass> nodes = new Stack<>();
        InOrderBinaryTreeNotRecursive.TreeNodeClass current = root;
        while (!nodes.isEmpty() || current != null) {
            if (current != null) {
                nodes.push(current);
                current = current.left;
            } else {
                InOrderBinaryTreeNotRecursive.TreeNodeClass node = nodes.pop();
                System.out.printf("%s ", node.data);
                current = node.right;
            }
        }
    }
}
//PrintingInorderTraversal
class Main{
    public static void main(String[] args) {
        InOrderBinaryTreeNotRecursive tree = new InOrderBinaryTreeNotRecursive();
        InOrderBinaryTreeNotRecursive.TreeNodeClass root = new InOrderBinaryTreeNotRecursive.TreeNodeClass("D");
        tree.root = root;
        tree.root.left = new InOrderBinaryTreeNotRecursive.TreeNodeClass("B");
        tree.root.left.left = new InOrderBinaryTreeNotRecursive.TreeNodeClass("A");
        tree.root.left.right = new InOrderBinaryTreeNotRecursive.TreeNodeClass("C");
        tree.root.right = new InOrderBinaryTreeNotRecursive.TreeNodeClass("E");
        tree.root.right.right = new InOrderBinaryTreeNotRecursive.TreeNodeClass("F");
        System.out.println();
        tree.inOrderWithoutRecursion();
        System.out.println();
    }
}

As mentioned earlier, the output is presented in ascending order.

A B C D E F

In inorder traversal, it pushes the root node first, followed by its left node.

  • Line 23: We make the left node current, and we continue it until we encounter a leaf.

  • Lines 25–27: Once we reach the leaf, we print it (mark it as traversed), followed by its parent and right node, and again continue traversing until ...