木鸟杂记

大规模数据系统

'Data Structures and Algorithms (I): Non-Recursive Binary Tree Traversal'

Posted on In

Overview

Recently, I’ve been thinking about some ideas and corresponding implementations for non-recursive tree traversal. I’m writing them down here for future reference.

Author: Muniao’s Notes https://www.qtmuniao.com. Please indicate the source when reposting.

Direct Iterative Approach

The basic idea is to keep going left until hitting a wall (encountering NULL), then turn back; move to the right child (the root of the right subtree), and continue going left (in a loop).

The basic code is as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
void traversal(TreeNode* root) {
    stack<TreeNode*> s;
    TreeNode* current = root;

    while (!s.empty() || current) {
        if (current) {
            s.push(current); //(1)
            current = current->left;
        } else {
            current = s.top()->right; // (3)
            s.pop(); // if we pop the node, then we do not have (5)
        }
    }
}

The corresponding complete traversal path is shown below:

1
2
3
4
      (1) root (5?)
         / (3)  \
        /        \
(2)l-subtree   (4)r-subtree

For any node root, there are three opportunities to visit it:

  1. Coming from the parent node (1)
  2. Returning after visiting the left subtree (3)
  3. Returning after visiting the right subtree (5)

Correspondingly, according to the definition of binary tree traversal:

  1. If the node is visited at (1), it is preorder traversal: root first (1), then left subtree (2), and finally right subtree (4).
  2. If the node is visited at (3), it is inorder traversal: left subtree first (2), then root (3), and finally right subtree (4).
  3. If the node is visited at (5), it is postorder traversal: left subtree first (2), then right subtree (4), and finally root (5).

Since we need to continue visiting the right subtree after finishing the left subtree, we need to save the pointer to root, which is the role of the stack here. As the traversal goes deeper, nodes are continuously pushed onto the stack, and the maximum length is the depth of the tree. It is worth emphasizing that as we return from visiting the left subtree, the stack will continuously pop, because after obtaining the pointer to the right subtree, there is no longer a need to save the pointer to root. Therefore, without special handling, step (5) does not exist.

Therefore, the non-recursive code for binary tree preorder and inorder traversal can be directly given as:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// preorder traversal:
void preorderTraversal(TreeNode* root) {
    stack<TreeNode*> s;
    TreeNode* current = root;

    while (!s.empty() || current) {
        while (current) {
            s.push(current); 
            cout << current->val << endl;//(1)
            current = current->left;
        }

        current = s.top()->right; 
        s.pop();
    }

    return ans;
}

// inorder traversal:
void inorderTraversal(TreeNode* root) {
    stack<TreeNode*> s;
    TreeNode* current = root;

    while (!s.empty() || current) {
        while (current) {
            s.push(current);
            current = current->left;
        }

        current = s.top()->right; 
        cout << s.top()->val << endl;//(3)
        s.pop();
    }
}

The code for postorder traversal is slightly more complex. The main modification required is: we cannot pop the stack after the second visit (i.e., (3) in the figure), but need to pop at stage (5). This raises the question of how to identify stage (5). My approach here is to introduce a prev pointer to mark the previous binary tree node in the visit sequence. If root->right is prev, or root->right is NULL, we can determine that we have returned from visiting the right subtree, which corresponds to stage (5).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void postorderTraversal(TreeNode* root) {
    stack<TreeNode*> s;
    TreeNode* current = root, *prev = NULL;

    while (current || !s.empty()) {
        while (current) {
            s.push(current);
            current = current->left;
        }

        TreeNode* now = s.top();
        if (now->right == NULL || now->right == prev) {
            // stage (5)
            cout << now->val;
            prev = now; // update the prev
            s.pop();
            current = NULL; // let the stack keep popping
        } else {
            // stage (4)
            current = now->right;
        }
    }
}

Simulating Recursion with a Stack

We know that a stack can be used to simulate function calls, or rather, function calls are essentially push and pop operations of function stack frames. Since binary tree traversal is simple enough, our simulation becomes relatively easy to implement.

For example, for preorder traversal, since the stack reverses the visiting order, we push the right subtree first.

1
2
3
4
5
6
7
8
9
10
11
12
void preorderTraversal(TreeNode* root) {
    stack<TreeNode*> s;
    if (root) s.push(root);
    while (!s.empty()) {
        TreeNode* now = s.top();
        cout << now->val;
        s.pop();

        if (now->right) s.push(now->right);
        if (now->left) s.push(now->left);
    }
}

If we push the left subtree first, it becomes an inverse postorder traversal. By adding another stack, we can obtain postorder traversal.

1
2
3
4
5
6
7
8
9
10
11
12
void inversePostorderTraversal(TreeNode* root) {
    stack<TreeNode*> s;
    if (root) s.push(root);
    while (!s.empty()) {
        TreeNode* now = s.top();
        cout << now->val;
        s.pop();

        if (now->left) s.push(now->left);
        if (now->right) s.push(now->right);
    }
}

Morris Inorder Traversal

For the traversal methods above, whether recursive or non-recursive, their extra space complexity is O(h), i.e., O(lg n), because the maximum stack overhead is the depth of the tree. So, is there a way to traverse a tree without using extra space? The astute reader might think of threaded binary trees. Bingo! This is the Morris inorder traversal.

Without further ado, here is the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void inorderTraversal(TreeNode* root) {
    TreeNode* current = root;
    while (current != NULL) {
        if (current->left == NULL) {
            cout << current->val;
            current = current->right;
        } else {
            TreeNode* prev = current->left;
            while (prev->right != NULL && prev->right != current) {
                prev = prev->right;
            }

            if (prev->right == NULL) {
                prev->right = current;
                current = current->left;
            } else if (prev->right == current) {
                cout << current->val;
                current = current->right;
                prev->right = NULL;
            }
        }
    }
}

The basic idea is:

1
2
3
4
5
6
7
8
9
1. Initialize current as root 
2. While current is not NULL
   If current does not have left child
      a) Print current’s data
      b) Go to the right, i.e., current = current->right
   Else
      a) Make current as right child of the rightmost node in current's left subtree
      b) Go to this left child, i.e., current = current->left

Well, this is actually pseudocode; see the source here. The core idea is that when we rush headlong into a dead end, in order to return painlessly, we need to punch a hole in the wall leading back to the original path, and fill the hole after passing through it. However, punching holes takes time; this is a typical trade-off of time for space—each time we have to waste a bit more time finding the rightmost node in the left subtree.

Summary

The essence of using a stack for binary tree traversal is: using the stack to save the access path (i.e., the path from the root node to the current node), so that when we can no longer proceed in the left subtree, we can backtrack and visit the right subtree.

我是青藤木鸟，一个喜欢摄影、专注大规模数据系统的程序员，欢迎关注我的公众号：“木鸟杂记”，有更多的分布式系统、存储和数据库相关的文章，欢迎关注。 关注公众号后，回复“资料”可以获取我总结一份分布式数据库学习资料。 回复“优惠券”可以获取我的大规模数据系统付费专栏《系统日知录》的八折优惠券。

我们还有相关的分布式系统和数据库的群，可以添加我的微信号：qtmuniao，我拉你入群。加我时记得备注：“分布式系统群”。 另外，如果你不想加群，还有一个分布式系统和数据库的论坛（点这里），欢迎来玩耍。

wx-distributed-system-s.jpg

不妨一读