Algorithm Cheat Sheet: Binary Tree Iterative Traversal

Binary tree traversal is a perfect case to show the power of recursive algorithms which enable straightforward and trivial implementations of all three traversal styles (in-order, pre-order, and post-order). Nevertheless, recursion is not the focus of this article. Instead, we are looking into how to do traversals iteratively.

The rationale of recursion is to call the same function recursively and rely on stacks to save and restore states of the current function execution before and after calling the same function again. Such stack operations are transparent to programmers under recursion whereas for iterating we need to manually implement them. Our demonstration of binary trees here is based on the representation with linked lists.

Examples:

In-order traversal

The sequence of an in-order traversal is left, root, and right.

  1. The in-order traversal first visits the leftmost node of a tree. Therefore, we first push the whole chain of left nodes to the stack until we reach the leftmost node.
  2. We visit the leftmost node reached in Step 1. This node is also the root of the branch fanning out from it. Therefore, the next traversal starts from its right branch.
  3. We then move on to the right node of the node visited in Step 2.
    • If that right node is null, as long as the stack is not empty, we pop out one node from the stack and repeat the process from Step 2.
    • Otherwise, we use that not-null right node as the new root and repeat the process from Step 1 to the branch fanning out from it.
stack<TreeNode*> st;
TreeNode *node = root;
while (node || !st.empty())
{
    if (node)
    {
        // Step 1.
        st.push(node);
        node = node->left;
    }
    else
    {
        // Step 2.
        node = st.top(); // Here the stack will not be empty.
        st.pop();
        Visit(node->val)

        // Step 3.
        node = node->right;
    }
}

Pre-order traversal

The sequence of a pre-order traversal is root, left, and right.

  1. The pre-order traversal first visits the root of a tree. Since we always start from the root of a tree, we just visit it.
  2. We traverse the left branch before the right branch. We therefore save the right node to the stack if it’s not null.
  3. We then move on to the left node of the node visited in Step 1. If that left node is null, as long as the stack is not empty, we pop out one node from the stack. Once we have a node ready that is not null, which is also the root of the branch tree fanning out from it, we repeat the process from Step 1.
stack<TreeNode*> st;
TreeNode *node = root;
while (node)
{
    // Step 1.
    Visit(node->val);

    // Step 2.
    if (node->right)
        st.push(node->right);

    // Step 3.
    node = node->left;
    if (!node && !st.empty())
    {
        node = st.top();
        st.pop();
    }
}

Post-order traversal

The sequence of a post-order traversal is left, right, and root. It can be derived from the in-order traversal.

  1. The post-order traversal first visits the leftmost node of a tree. Similar to the in-order traversal, we first push the whole chain of left nodes to the stack until we reach the leftmost node.
  2. The leftmost node reached in Step 1 is also the root of the branch fanning out from it. Since it’s the leftmost node, it has no left node. If it has no right node either, we are ready to visit it. Once we visit it, we pop it out of the stack.
  3. We then move on to the right node of the node processed in Step 2.
    • If that right node is null, as long as the stack is not empty, we peek the top node from the stack and repeat the process starting from Step 2 to it.
    • Otherwise, we use that not-null right node as the new root and repeat the process from Step 1 to the branch fanning out from it. Note that we also need to nullify the right node pointer of the original root to prevent an infinite loop of the traversal.
stack<TreeNode*> st;
TreeNode *node = root;
while (node || !st.empty())
{
    if (node)
    {
        // Step 1.
        st.push(node);
        node = node->left;
    }
    else
    {
        // Step 2.
        node = st.top(); // Here the stack will not be empty.
        TreeNode *right = node->right;
        node->right = NULL;
        if (!right)
        {
            st.pop();
            Visit(node->val);
        }

        // Step 3.
        node = right;
    }
}

Interestingly, a post-order traversal can also be derived from the pre-order traversal. Recall that the sequence of a pre-order traversal is root, left, and right. If we swap the order of left and right, which becomes root, right, and left, the reversal of it is exactly the post-order traversal.

stack<TreeNode*> st;
TreeNode *node = root;
while (node)
{
    // Step 1.
    Visit(node->val);

    // Step 2.
    if (node->left)
        st.push(node->left);

    // Step 3.
    node = node->right;
    if (!node && !st.empty())
    {
        node = st.top();
        st.pop();
    }

    reverse(visitResult);
}

Contents