In my last post I started discussing trees and how to implement them. In this lesson we're going to be looking at how to traverse a tree structure to find a certain node. When it comes to traversing a tree there are two main methods, breadth-first search (BFS) or depth-first search (DFS).
Breadth-First Search
The name of the method is pretty self explanatory, you traverse the tree in layers. Starting at the top and working your way down left to right, visiting each node once as you go. In general, you want to use BFS when finding the shortest path from one node to another, or when the tree is wide.
An important problem that we need to address when searching through a tree is that nodes don't keep track of their parents or what is left or right of them, only their respective children. Take the above image for example, after navigating from node 1 to node 2, how do we get to 3? Node 2 only has information regarding node 5 and 6. The answer is another data structure that we've talked about in the past, a queue.
For this example we are going to continue using our binary search tree from our previous post. Now let's look at the code.
We start with our current node and add the value to our visited array. This can vary depend on what you want you want to accomplish. In this case we are just recording the values of each node. We then and add each child to our queue, from there we go to the next node in the queue and repeat the process until we've gone through each node in the tree.
The code for the post can be found here.
Top comments (0)