In-order traversal on a BST without recursion.

InOrder.java

import java.util.Stack;

public class InOrder {

    public static class TreeNode<T extends Comparable<T>> {
        public T data;
        public TreeNode<T> left, right;

        public TreeNode(T data) {
            this(data, null, null);
        }
        
        public TreeNode(T data, TreeNode<T> left, TreeNode<T> right) {
            this.data = data;
            this.left = left;
            this.right = right;
        }
    }

    public interface TraversalCallback<T extends Comparable<T>> {
        // called by the traversal algorithm when a node is processed;
        // return true if to keep traversing, and false to signal otherwise
        public boolean visit(TreeNode<T> node);
        // called by the traversal algorithm when all nodes have been processed;
        // if traversal was abruptly ended by visit() returning false, this callback
        // is not going to be called
        public void end();
    }

    // traverse a binary search tree, in order, starting from the given root;
    // caller supplies a callback object to specify what to do when a node is processed
    public static <T extends Comparable<T>> void visitInOrderTraversal(
            TreeNode<T> root, TraversalCallback<T> callback) {
        if (root == null)
            return;

        Stack<TreeNode<T>> stack = new Stack<TreeNode<T>>();

        TreeNode<T> current = root;
        while (current != null) {
            stack.push(current);
            current = current.left;
        }

        while (true) {
            if (stack.empty()) {
                callback.end();
                break;
            }

            current = stack.pop();
            if (!callback.visit(current)) {
                return;
            }

            current = current.right;
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
        }
    }

    // traverse a binary search tree, in order, by printing the node data for each node visited
    public static <T extends Comparable<T>> void printInOrderTraversal(TreeNode<T> root) {
        // create the callback the print out each node's data as it is processed by the traversal algorithm
        TraversalCallback<T> callback = new TraversalCallback<T>() {
            @Override
            public boolean visit(TreeNode<T> node) {
                System.out.print(node.data + " ");
                return true;
            }
            @Override
            public void end() {
                System.out.println();
            }
        };

        // call the actual in-order traversal algorithm, with the above callback
        visitInOrderTraversal(root, callback);
    }

    public static <T extends Comparable<T>> void printKthSmallest(TreeNode<T> root, int k) {
        if (k <= 0) {
            throw new IllegalArgumentException("Illegal argument: " + k);
        }

        final int max = k;

        // create the callback that keeps track of how many nodes have been visited so far
        TraversalCallback<T> callback = new TraversalCallback<T>() {
            private int visited = 0;
            @Override
            public boolean visit(TreeNode<T> node) {
                visited++;
                if (visited == max) {
                    System.out.println("" + node.data);
                    return false;
                }
                return true;
            }
            @Override
            public void end() {
                throw new IndexOutOfBoundsException("There are less than " + max + " nodes in the tree!");
            }
        };

        // call the actual in-order traversal algorithm, with the above callback
        visitInOrderTraversal(root, callback);
    }

    public static void main(String[] args) {
        Integer[] sampleData = {1, 3, 2, 5, 4};
        TreeNode<Integer> root = createBinarySearchTreeFromArray(sampleData);

        System.out.print("In order traversal: ");
        printInOrderTraversal(root);

        System.out.print("1st smallest item: ");
        printKthSmallest(root, 1);
        System.out.print("3rd smallest item: ");
        printKthSmallest(root, 3);
        System.out.print("5th smallest item: ");
        printKthSmallest(root, 5);
    }

    // helper functions below

    private static <T extends Comparable<T>> TreeNode<T> createBinarySearchTreeFromArray(T[] array) {
        if (array.length == 0) {
            return null;
        }

        TreeNode<T> root = new TreeNode<T>(array[0]);
        for (int i = 1; i < array.length; i++) {
            insertIntoBinarySearchTree(root, array[i]);
        }

        return root;
    }

    private static <T extends Comparable<T>> TreeNode<T> insertIntoBinarySearchTree(TreeNode<T> node, T item) {
        if (item.compareTo(node.data) == 0) {
            throw new IllegalArgumentException("Duplicate item detected: " + item.toString());
        } else if (item.compareTo(node.data) < 0) {
            if (node.left == null) {
                node.left = new TreeNode<T>(item);
                return node.left;
            } else {
                return insertIntoBinarySearchTree(node.left, item);
            }
        } else {
            if (node.right == null) {
                node.right = new TreeNode<T>(item);
                return node.right;
            } else {
                return insertIntoBinarySearchTree(node.right, item);
            }
        }
    }

}