Programming Discrete Math Concepts for Beginners/

...

/

Inorder Traversal

Inorder Traversal

Learn more about inorder traversal and how to code it iteratively and recursively.

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.

Press + to interact
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), ...