Search in BSTs

We mentioned in the previous lesson that ordering keys using the search-tree property allows us to write efficient tree algorithms. The foremost example of this is searching for the node with a given key (also known as a lookup or a get).

Since a BST is a dictionary, we often want to know: what is the item (or value) associated with a given key k? The search algorithm pseudocode is as follows:

• If k is equal to the root node's key, return the root node's item
• Else if k is less than the root node's key, search in the left subtree
• Else (k is greater than the root node's key), search in the right subtree

This logic can be applied recursively at each level of the tree. Since we know the ordering of the keys, we can ignore entire subtrees where k could not possibly be! This allows the search algorithm to follow a single path, starting from the root node and ending at the node with the key k (if it exists).

Implementing search in a BST

Watch the video below to see the definition of a LinkedBST class that we will use for illustrating a binary search tree, as well as the implementation of the search() method: