Tree Traversal (Inorder, Preorder and Postorder) in Java

Inorder, preorder and postorder are the three ways of walking through a binary tree depth first. They differ only in one thing: when you look at the root compared with its two subtrees. Once that clicks, all three are the same five lines of code with one line moved.

The tree we will use

          10
        /    \
      20      30
     /  \    /  \
   40   50  60   70

The three orders

• Inorder (left, root, right): 40 20 50 10 60 30 70
• Preorder (root, left, right): 10 20 40 50 30 60 70
• Postorder (left, right, root): 40 50 20 60 70 30 10

An easy way to remember them is by where the word puts the root: pre means before the children, post means after them, and in means in between.

Walking through inorder by hand

Start at 10. Inorder says "do the left subtree first", so go to 20, and again to 40. 40 has no left child, so print 40, then try its right child, which is empty. Back at 20: the left side is done, so print 20, then go right and print 50. Now the whole left subtree of 10 is finished, so print 10, and repeat the same steps on the right: 60, 30, 70.

When each one is useful

• Inorder on a binary search tree gives the values in sorted order. This is the usual way to check whether a tree is a valid BST.
• Preorder visits a parent before its children, so it is used to copy a tree or to save it to a file and rebuild it later.
• Postorder handles the children before the parent. Use it when a node needs results from below it, for example deleting a tree, or computing the height or size of every subtree.

Solution in Java

The recursive versions below match the definitions exactly. We have also added an iterative inorder traversal with an explicit stack, because interviewers often ask for it once you have written the recursive one.

import java.util.ArrayDeque;
import java.util.Deque;

class Node {
    int key;
    Node left, right;
    Node(int key) { this.key = key; }
}

public class TreeTraversal {
    static void inOrder(Node root) {
        if (root == null) return;
        inOrder(root.left);
        System.out.print(root.key + " ");
        inOrder(root.right);
    }

    static void preOrder(Node root) {
        if (root == null) return;
        System.out.print(root.key + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    static void postOrder(Node root) {
        if (root == null) return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.key + " ");
    }

    // Inorder without recursion, using an explicit stack
    static void inOrderIterative(Node root) {
        Deque<Node> stack = new ArrayDeque<>();
        Node curr = root;
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            System.out.print(curr.key + " ");
            curr = curr.right;
        }
    }

    public static void main(String[] args) {
        //          10
        //        /    \
        //      20      30
        //     /  \    /  \
        //   40   50  60   70
        Node root = new Node(10);
        root.left = new Node(20);
        root.right = new Node(30);
        root.left.left = new Node(40);
        root.left.right = new Node(50);
        root.right.left = new Node(60);
        root.right.right = new Node(70);

        System.out.println("Inorder traversal");
        inOrder(root);
        System.out.println();
        System.out.println("Preorder traversal");
        preOrder(root);
        System.out.println();
        System.out.println("Postorder traversal");
        postOrder(root);
        System.out.println();
        System.out.println("Inorder traversal (iterative)");
        inOrderIterative(root);
        System.out.println();
    }
}

Output

Inorder traversal
40 20 50 10 60 30 70
Preorder traversal
10 20 40 50 30 60 70
Postorder traversal
40 50 20 60 70 30 10
Inorder traversal (iterative)
40 20 50 10 60 30 70

(The older version of this code printed the label "Inorder Traversal" above the postorder result by mistake. That is fixed now.)

Complexity

Every node is visited exactly once, so all of these run in O(n) time. The extra space is the depth of the recursion, or the size of the stack in the iterative version, which is O(h) where h is the height of the tree.

Practice

Try writing preorder iteratively as well (it is easier than inorder: push right child first, then left). Then try finding the maximum node in a binary tree, and check your understanding with the trees and BST MCQs.

Tip: try to solve the problem yourself before reading the solution. Use the code as a reference to check your approach, and make sure you understand why it works.

More data structures tutorials All coding problems MCQ practice