Binary Tree Iterative Traversal

algorithm cheat sheet

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). Given its simplicity, recursion is not the focus of this article. Instead, we are looking into how to do it 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 iteration 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. An in-order traversal first visits the leftmost node of a binary tree. Starting from the root, we first push the whole chain of left nodes to the stack.
  2. We then visit the leftmost node collected in Step 1. This node is also the root of the branch fanning out from it.
  3. Since the node visited in Step 2 doesn’t have the left node (because it’s the leftmost node), the next traversal starts from its right node.
    • 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.
// "root" is the root node of the given binary tree for 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.
        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. A pre-order traversal first visits the root of a binary tree. Since we always start from the root of a binary tree, we just visit it.
  2. A pre-order traversal then traverses 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 root 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.
// "root" is the root node of the given binary tree for traversal.
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. A 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.
  2. The leftmost node collected in Step 1 is also the root of the branch fanning out from it. Since it’s the leftmost node, it has no left nodes. We visit that node only if it doesn’t have the right node either (once we visit it, we pop it out of the stack).
  3. We then move on to the right node of the leftmost node collected in Step 1.
    • 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. Note that we also need to nullify the right node pointer of the original root to prevent an infinite loop of the traversal.
// "root" is the root node of the given binary tree for 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.

// "root" is the root node of the given binary tree for 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