Iterative Preorder Binary Tree Traversal

The typical definition of a preorder binary tree traversal is that you will first visit the top node, all nodes left of the tree, and then work your way back up the tree visiting the right nodes.

The typical recursive preorder binary tree traversal is this:

private void preorderTraversal(IntegerNode integerNode) {
    if (integerNode == null) {
        return;
    }
    System.out.print(integerNode.value + "\t");
    preorderTraversal(integerNode.left);
    preorderTraversal(integerNode.right);
}

Notice how we first check the current node, recurse through the left nodes, and then work our way back up the tree visiting the right nodes.

Whenever you have to rewrite recursion to iteration, you should be thinking “Stack”. This is because each recursive function call is really just an element that is pushed onto the stack behind the scenes.

Here is this same algorithm written to use iteration:

private void iterativePreorderTraversal(IntegerNode integerNode){
    Stack<IntegerNode> integerNodeStack = new Stack<>();
    integerNodeStack.push(integerNode);


    while(!integerNodeStack.isEmpty()){
        IntegerNode integerNodeIterator = integerNodeStack.pop();

        System.out.print(integerNodeIterator.value + "\t");

        if(integerNodeIterator.right != null){
            integerNodeStack.push(integerNodeIterator.right);
        }
        if(integerNodeIterator.left != null){
            integerNodeStack.push(integerNodeIterator.left);
        }

    }
}

We can think logically about this algorithm and trace through it to help us achieve a better understanding. First, the first node that will be popped off the stack will be the top of the binary tree (in this case the integerNode method argument). Second, we will keep adding the right and left nodes provided either of them are not null. The most important part to notice at this stage is that all left elements will be popped before any right elements because the stack data-structure guarantees the LIFO (last in first out) property. In our case, the current iteration will always have the left node being pushed into the stack after the right node, provided the left node is not null. After we have exhausted all the left nodes, we will start climbing back up the tree.

Feel free to leave any questions or comments below.