Traversing (or walking) a tree is the process of visiting all nodes of a tree and performing an operation at each node. But how should we do that? Should we start from the top of the tree or from the bottom? From the left or the right side? There are three different approaches that can be used to visit all the nodes in a tree: in-order, pre-order, and post-order.
In the following sections, we will deep dive into the uses and implementations of these three types of tree traversals.
An in-order traversal visits all the nodes of a BST in ascending order, meaning it visits the nodes from the smallest to largest. An application of in-order traversal would be to sort a tree. Let's check out its implementation:
this.inOrderTraverse = function(callback){
inOrderTraverseNode(root, callback); //{1}
};The inOrderTraverse method receives a callback function as a parameter. This function can be used to perform the action we would like to execute when the node is visited...