Think about Array. This linear DS has only, commonly used and logical way of visiting all its elements. Situation with Trees is slightly different because there is no one, valid method to walk through whole structure. There are few, and they fall into two main categories. Each of these algorithms is suitable for different needs, stay with me to learn them all.
Depth-First Search
The first family of traversing algorithms is called Depth-First Search (DFS). Mind the word depth because it says everything about the idea of how it visits Nodes - walk starts on the Root and dives to the deepest Node in a given branch. You can think of it like “vertical” or “top-to-bottom” type of search. What differs methods presented below is a moment when Root Node is visited.
In-Order
In this method we start the walk from the left Subtree. First node visited will be the left-most one, then you have to climb up to the parent and visit its right Child if exists. If so, please remember that if parent has left Child it must be visited first up until the Root. When it is reached, you start all over but with the right Subtree keeping in mind that you always start with a left-most element.
Usage
Pay attention to the Walked Path shown above. As you can see, Nodes were visited from these holding smallest value up to those with the greatest. This is applicable only for Binary Search Trees since In-order, how its name suggest, traverse the structure in the same sequence(order) as during creation.
Pre-Order
Pre-order is very similar to the previous method but with one exception - walk starts from the Root, not form the left-most element in a left Subtree. After visiting Root Node the rest of the process is the same as in case of In-order, start with left and move towards right.
Usage
This algorithm is the best choice when you need to check Root Nodes before their Leaves. Thanks to this there is no need to visit Leaf Nodes, especially when you know that value you’re looking for is not there.
Another practical usage is making a copy of the Tree. Nodes traversed this way and then inserted into new structure will create an identical Tree.
Post-Order
Last method leaves visiting a Root Node for the dessert. It starts on the left Subtree, then moving to the right. What is important here is that it moves from the left-most Node to the deepest left Children, and after reaching the Leaf on the highest level it visits right Children from previous, “passed-by” Nodes.
Usage
Use this method if you are sure that Data you are looking for exists in Leaf Node. Since it takes care of these elements in a first place we don’t need to waste time for visiting non-leaf Nodes. Method is also useful when it comes to removing Nodes or the whole Tree in bottom-top manner.
Breadth-First Search
Breadth means the distance or measurement from side to side, within some range. DFS is walking the Tree from top to bottom, Breadth-First Search (BFS) does the opposite. Instead of diving to the very bottom of the structure it crawls level by level, starting with Root Node (level 0) and then walking through levels from their left to the right side.
Usage
It turns out that BFS can be applied to solve many problems:
- finding the shortest path between Nodes
- locating the nearest neighbouring Nodes (great in navigation or P2P networks)
- reaching all Nodes (network broadcast)