Scenario
We have been asked to write code to implement an algorithm that searches the binary tree one level at a time, left to right. The traversal starts from the root node and finishes at the leaf nodes.
Aim
To apply BFS traversal in Java.
Steps for Completion
- Implement the algorithm shown in the preceding code in Java.
- Use the Java LinkedList collection to implement the queue shown in the pseudocode. The method signature should be as follows:
public void printBfs()
In this section, we have learned about the various ways we can traverse a binary tree and the different ordering produced by each strategy. We have also seen how these algorithms can be implemented both in a recursive and in an iterative manner. In the next section, we will discuss a more restrictive type of binary search tree that ensures our data structure maintains a good performance, even in the worst input case.