Searching

This section will cover some ways to find values in a set.

Binary Search

Binary Search # Binary search is a way of finding a specific node in a tree. It only works on binary trees due to its helpful sorted property. It simply traverses the tree, moving left if the current node is too large or right if it is too small. Binary search runs in $\Theta(\log(n))$ time for bushy trees, which is also the number of layers in a tree. The Algorithm # public BST find(BST T, Key sk) { if (T == null) { return null; } if (sk.

Breadth First Search (DFS)

Breadth First Search (BFS), like Depth First Search (DFS), is a method of traversing a graph. BFS simply traverses in a different order, but otherwise is very similar to DFS. The main difference is that BFS visits all children before any subgraphs. In a tree, we call this level order. For the example tree above, a level order traversal would go in this order: D B F A C E G.

Depth First Search (DFS)

Depth First Traversal # Before we move on to searching, let’s talk about traversing. Traversal is the act of visiting nodes in a specific order. This can be done either in trees or in graphs. For trees in particular, there are three main ways to traverse. The first way is inorder traversal, which visits all left children, then the node itself, then all right children. The end result should be that the nodes were visited in sorted order.