Learning JavaScript Data Structures and Algorithms - Third Edition

Post-order traversal

A post-order traversal visits the node after it visits its descendants. An application of post-order traversal could be computing the space used by a file in a directory and its subdirectories.

Let’s take a look at its implementation:

postOrderTraverse(callback) {
  this.postOrderTraverseNode(this.root, callback);
}

The postOrderTraverseNode implementation is declared as follows:

postOrderTraverseNode(node, callback) {
  if (node != null) {
    this.postOrderTraverseNode(node.left, callback); // {1}
    this.postOrderTraverseNode(node.right, callback); // {2}
    callback(node.key); // {3}
  }
}

In this case, the post-order traversal will visit the left node ({1}), then the right node ({2}), and finally, the root node ({3}).

The algorithms ...