This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

Let’s review the order of front, middle, and back traversal of binary trees:

  1. Front traversal order: middle – left – right
  2. Middle order Traversal order: left-middle-right
  3. Back-order traversal order: left-right-center

It is very easy to write binary tree traversal recursively. For example, the code for pre-traversal is as follows:

const result = []
function preorderTraversal(node) {
    if(! node)return null
    result.push(node.val)
    preorderTraversal(node.left)
    preorderTraversal(node.right)
}

preorderTraversal(root)
Copy the code

As we all know, when a function is called, the system maintains corresponding variables (parameters, local variables, return addresses, and so on) on the stack for each function.

For example, if there are three functions a, B, and C, a calls A, A calls B, and B calls C. The call stack at this point is shown as follows:

Why do you say that? That’s how recursive traversal works, except that the function keeps calling itself until it hits a recursive exit (termination condition).

For example, the following binary tree is now traversed recursively:

1\2/3Copy the code

Its traversal order is 1-2-3, and the call stack is shown as follows:

Now that we understand the recursive call stack, let’s see how we can use recursive ideas to implement sequential iteration:

function preorderTraversal(root) {
    const result = []
    // Use an array stack to simulate the call stack
    const stack = []
    let node = root
    while (stack.length || node) {
        // Recursively traverse the left subtree of the node until it is empty
        while (node) {
            result.push(node.val)
            stack.push(node)
            node = node.left
        }
        // Node is empty when exiting the loop due to the nature of pre-traversal
        // The last node of the current node must be its parent node
        // Now that the left subtree has reached its end, it is time to traverse the right subtree of the parent node
        // So eject the parent node and start a new loop from its right subtree
        node = stack.pop()
        node = node.right
    }

    return result
}
Copy the code

To see another concrete example, run through it with iterative traversal:

            1
          /    \
         2      3
        /  \   /  \
       4    5 6    7
Copy the code
  1. The initial node node is 1
  2. The while iterates through its left child
  3. The currentStack = = 4-trichlorobenzene [1]
  4. The initial node has traversed the last left child below it, the left child of node 4, so now it is time to traverse the right child of node 4
  5. Eject node 4 and start a new loop from its right child
  6. Since the right child of node 4 is empty, the while loop is not entered, and then the parent node 2 of node 4 is ejected
  7. The loop starts at the right child of node 2

See, does this already show that the iterative traversal is exactly the same as the recursive traversal?

And the advantage of using recursion to do iterative traversal is that it’s easy to understand, and you’ll be able to remember how to do it in the future.

In the sequence traversal

Middle-order traversal is similar to pre-order traversal, except that the value of the node is pushed into result only when the node is removed from the stack.

function inorderTraversal(root) {
    const result = []
    const stack = []
    let node = root
    while (stack.length || node) {
        while (node) {
            stack.push(node)
            node = node.left
        }
        
        node = stack.pop()
        result.push(node.val)
        node = node.right
    }
    
    return result
}
Copy the code

After the sequence traversal

The forward traversal process is middle-left-right, and the reverse forward traversal process is to switch the order of traversing the left and right subtrees, namely, middle-right-left.

And then if you look at the post-order traversal left-right-middle, you can see that the reverse of the pre-order traversal is the post-order traversal.

The post-order traversal code written using this feature is as follows:

function postorderTraversal(root) {
    const result = []
    const stack = []
    let node = root
    while (stack.length || node) {
        while (node) {
            result.push(node.val)
            stack.push(node)
            node = node.right // Node. left is node.right
        }

        node = stack.pop()
        node = node.left // Node. right, node.left
    }
    
    return result.reverse() // The reverse of the backward traversal order is the order of the backward traversal
}
Copy the code

The resources

  • Here he is. Here he is with his three brothers, traversing the uniform algorithm in front, middle and back order

Please feel free to discuss in the comments section. The nuggets will draw 100 nuggets in the comments section after the diggnation project. See the event article for details.