Trick: Traverse Binary Tree with Stack

labuladongOriginalAbout 4400 words

Prerequisites

Before reading this article, you need to learn:

This Content is for Extension Only

Generally, recursive traversal or level-order traversal is sufficient for handling binary trees.

The stack-based iterative traversal method introduced in this article is essentially a manual simulation of the recursive process using a stack. This method is not required for other problems on this website, and it is also rarely asked in interviews.

Therefore, the content of this article is solely for expanding your thinking, and you are not required to master it. If you are not interested, feel free to skip the content of this article.

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:

java 🟢

List<TreeNode> traverse(TreeNode root);

cpp 🤖

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

python 🤖

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

go 🤖

func traverse(root *TreeNode) []*TreeNode

javascript 🤖

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:

java 🟢

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
}

cpp 🤖

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
}

python 🤖

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

go 🤖

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
}

javascript 🤖

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:

java 🟢

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
        }
    }
}

cpp 🤖

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
        }
    }
}

python 🤖

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

go 🤖

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
        }
    }
}

javascript 🤖

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 a recursive algorithm into an iterative one, I can simply copy and paste the code corresponding to the pre-order, in-order, and post-order positions from the recursive solution into the iterative framework, and it will run directly, yielding the correct result.

Theoretically, all recursive algorithms can be transformed into iterative forms using a stack, because computers inherently use a stack to iterate and execute recursive functions.

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

Converting Recursive Framework to Iterative

According to the Binary Tree Mindset (Outline), in the recursive framework of a binary tree, the pre-order, in-order, and post-order traversal positions correspond to specific timing points:

The code at the pre-order traversal position will execute just after the current node root is visited and before traversing the left and right subtrees of root;

The code at the in-order traversal position will execute after the left subtree of the current node root has been traversed and just before starting to traverse the right subtree of root;

The code at the post-order traversal position will execute after the entire subtree rooted at the current node root has been traversed.

This conclusion is easily understandable from the perspective of recursive code:

Trick: Traverse Binary Tree with Stack

Converting Recursive Framework to Iterative

Iterative Code Framework