There are many traversal methods of binary tree. This paper analyzes the pre-order, middle-order and post-order non-recursive traversal of binary tree. The code is written in javascript.

1 The following is the data structure of binary tree

let root = {
    val: 1,
    left: {
        val: 2,
        left: {
            val: 3
        },
        right: {
            val: 4
        }
    },
    right: {
        val: 5,
    }
}
Copy the code

  • Sequential traversal results (left and right roots) : 1, 2, 3, 4, 5, 6
  • Middle order traversal results (left root right) : 3, 2, 1, 5, 4, 6
  • The result of back-order traversal (left and right roots) : 3, 2, 5, 6, 4, 1

The differences between the three traversal methods are as follows

  • Preordering: After traversing a node, output the value of the node and continue traversing the left and right subtrees
  • Middle sequence: Traverses a node, stores it temporarily, outputs the value of the node after traversing the left subtree, and traverses the right subtree again
  • Post-order: Traverses a node, stores it temporarily, and outputs the value of the node after traversing the left and right subtrees

2 Order traversal first

Declare two variables stack, result, type array; Stack is used to store nodes traversed, and result is used to store the value of the current node. The general idea is to determine the order of stack loading and unloading. For example, sequential traversal is performed to traverse the binary tree, and the current node value is saved to result before temporary storage. The left subtree traversal is performed until it is empty before unloading the stack, and the same operation is performed on the right node of the current node.

Here’s the idea:

  • Take the heel node as the target node and start traversal
  • 1. Access the value of the target node
  • 2. Push the left subtree to the node whose left subtree is empty
  • 3. Remove the node from the stack, use the right subtree as the target node, and perform 1, 2, and 3 in sequence
function test2(root) {
    let stack = [];
    let result = [];
    while(root || stack.length > 0) {
        while(root) {
            result.push(root.val);
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        root = root.right;
    }
    return result;
}
Copy the code

2. Order traversal

Here’s the idea:

  • Take the heel node as the target node and start traversal
  • 1. Push the left subtree to the node whose left subtree is empty
  • 2. Remove the node from the stack -> Access the node
  • 3. Use the right subtree as the target node, and perform 1, 2, and 3 in sequence
function test(root) {
    let result = [];
    let stack = [];
    while(root || stack.length > 0) {
        while(root) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        result.push(root.val);
        root = root.right;
    }
    return result;
}
Copy the code

3 Order traversal

Post-order traversal is a little different from pre-order and middle-order traversal. The reason for the difference is that after traversing the left subtree, if the current traversal of the last node has a right subtree, it also needs to traverse the right subtree.

function test(root) { const result = []; const stack = []; let last = null; while (root || stack.length > 0) { while (root) { stack.push(root); root = root.left; } root = stack[stack.length - 1]; if (! root.right || root.right === last) { root = stack.pop(); result.push(root.val); last = root; root = null; } else { root = root.right; } } return result; }Copy the code