Traversing a binary tree is the process of stepping through each node of the tree and performing some sort of action on the data contained in the node (such as printing the key value pair). There are two main techniques to perform tree traversal: depth-first search and breadth-first search, more commonly known as DFS and BFS, respectively.

In depth-first search, the algorithm goes down a path of tree nodes until it cannot go any further. Once it cannot go further, it backtracks and discovers any remaining unexplored branches. A recursive implementation is shown in the following code. In this traversal method, a different output sequence is produced depending on where the action is executed in the method.

In a preorder execution, we perform the action immediately, as soon as a new node is discovered. A postorder execution, on the other hand, is when both children of a node have been explored and we're about to backtrack. An inorder execution is done when the left child has been processed but before processing the right one. When using an inorder traversal, the keys in the binary search trees will be processed in ascending order:

public void printDfs() {
  Optional.ofNullable(root).ifPresent(this::printDfs);
}
private void printDfs(BinaryTreeNode<K, V> node) {
  //System.out.println("PREORDER " + node.getKey());
  node.getLeft().ifPresent(this::printDfs);
  System.out.println("INORDER " + node.getKey());
  node.getRight().ifPresent(this::printDfs);
  //System.out.println("POSTORDER " + node.getKey());
}  

In the breadth-first search traversal, the algorithm explores the binary tree one level at a time, left to right. The traversal starts from the root node and finishes at the leaf nodes. The output of an example binary tree is shown in Figure 3.11. To implement a BFS traversal of a binary tree, we can make use of a queue initialized to contain the root node. Then, while the queue is not empty, we read the first node on the queue, process it, and add first the left and then the right child to the queue:

We show the pseudocode of this as follows:

breadthFirstSearch(root)
  if (root != null)
    queue = createQueue()
    enqueue(queue, root)
    while (not isEmpty(queue))
      node = dequeue(queue)
      process(node)
      if (node.left != null) enqueue(queue, node.left)
      if (node.right != null) enqueue(queue, node.right)