Trick: Traverse Binary Tree with Stack

labuladongOriginalAbout 4382 words

Prerequisites

Before reading this article, you should first study:

Content for Expansion Only

Typically, using recursive or level-order traversal methods is sufficient for handling binary trees.

This article introduces a stack-based iterative method for traversing binary trees, which essentially simulates recursion manually with a stack. This method is not needed for other exercises on this site, and interviewers rarely require you to write such code during interviews.

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

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

Some readers have asked me how to convert pre-order, in-order, and post-order recursive frameworks into iterative forms. I have memorized some iterative templates for binary tree traversal in the past; they are short and easy to remember but lack versatility.

The lack of versatility means that the templates are specifically for "returning pre-order/in-order/post-order traversal results of a binary tree in an iterative way," with function signatures like this that return 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