Trick: Traverse Binary Tree with Stack

DFS/BFS Traversal of Binary Trees introduced recursive traversal and level-order traversal methods for binary trees, which are the simplest and most practical methods.

Some readers have asked me how to convert the recursive framework for preorder, inorder, and postorder traversals into an iterative form. I used to memorize some code templates for implementing iterative preorder, inorder, and postorder traversals of binary trees. These templates are relatively short and easy to remember, but they lack generality.

Lacking generality means that the templates are only designed for the specific problem of "using an iterative approach to return the preorder/inorder/postorder traversal results of a binary tree," with a function signature similar to this, returning a list of TreeNode:

List<TreeNode> traverse(TreeNode root);

vector<TreeNode*> traverse(TreeNode* root);

def traverse(root: TreeNode) -> List[TreeNode]:

func traverse(root *TreeNode) []*TreeNode

var traverse = function(root) {
};

If given some slightly more complex binary tree problems, such as Lowest Common Ancestor or Maximum Sum of Binary Search Subtree Keys, you might find it challenging to convert these recursive solutions into iterative ones.

What I want is a universal template that can transform any binary tree recursive algorithm into an iterative one.

In other words, something similar to a binary tree recursive framework:

void traverse(TreeNode root) {
    if (root == null) return;
    // the position of preorder traversal code
    traverse(root.left);
    // the position of inorder traversal code
    traverse(root.right);
    // the position of postorder traversal code
}

void traverse(TreeNode* root) {
    if (root == NULL) return;
    // the position of preorder traversal code
    traverse(root->left);
    // the position of inorder traversal code
    traverse(root->right);
    // the position of postorder traversal code
}

def traverse(root):
    if not root:
        return
    # the position of preorder traversal code
    traverse(root.left)
    # the position of inorder traversal code
    traverse(root.right)
    # the position of postorder traversal code

func traverse(root *TreeNode) {
    if root == nil {
        return
    }
    // the position of pre-order traversal code
    traverse(root.Left)
    // the position of in-order traversal code
    traverse(root.Right)
    // the position of post-order traversal code
}

var traverse = function(root) {
    if (root === null) return;
    // the position of preorder traversal code
    traverse(root.left);
    // the position of inorder traversal code
    traverse(root.right);
    // the position of postorder traversal code
};

The iterative framework should also have positions for pre-order, in-order, and post-order code:

void traverse(TreeNode root) {
    while (...) {
        if (...) {
          // the position of preorder traversal code
        }
        if (...) {
          // the position of inorder traversal code
        }
        if (...) {
          // the position of postorder traversal code
        }
    }
}

void traverse(TreeNode* root) {
    while (...) {
        if (...) {
          // the position of preorder traversal code
        }
        if (...) {
          // the position of inorder traversal code
        }
        if (...) {
          // the position of postorder traversal code
        }
    }
}

def traverse(root: TreeNode):
    while (...):
        if (...):
          # code position for pre-order traversal
        if (...):
          # code position for in-order traversal
        if (...):
          # code position for post-order traversal

func traverse(root *TreeNode) {
    for .... {
        if ... {
            // the position of preorder traversal code
        }
        if ... {
            // the position of inorder traversal code
        }
        if ... {
            // the position of postorder traversal code
        }
    }
}

var traverse = function(root) {
    while (...) {
        if (...) {
          // the position of preorder traversal code
        }
        if (...) {
          // the position of inorder traversal code
        }
        if (...) {
          // the position of postorder traversal code
        }
    }
}

If I want to convert recursion to iteration, I can simply copy and paste the code from the preorder, inorder, and postorder positions of the recursive solution into the iterative framework. This will run directly and produce the correct result.

Theoretically, all recursive algorithms can be converted to an iterative form using a stack, because a computer essentially uses a stack to iteratively execute recursive functions.

In this article, we will use a "stack" to simulate the process of function recursion and summarize a general iterative traversal framework for binary trees.

Converting Recursion to Iteration

According to the Binary Tree Mindset (Guiding Principles), in the recursive framework of a binary tree, the positions of preorder, inorder, and postorder traversals are specific time points:

The code at the preorder traversal position executes just when the current node root is reached, before traversing the left and right subtrees of root.

The code at the inorder traversal position executes after traversing the left subtree of the current node root and just before starting to traverse the right subtree of root.

The code at the postorder traversal position executes after traversing the entire subtree rooted at the current node root.

From the perspective of recursion code, the above conclusions are quite easy to understand: