1.12. Searching in Binary Search Trees

So, what we are going to look at today and binary search trees and in a binary search tree we are going to argue that all of these operations are actually logarithmic, provided we maintain the binary search tree with a good structure.

In this section, we introduce binary search trees (BST) as a specific type of binary tree. The key property of a binary search tree is that it is organized in such a way that the operations of searching, inserting, and deleting values can all be performed efficiently, generally in logarithmic time, which is significantly faster than linear time for large datasets. We also emphasize the importance of maintaining a balanced BST to ensure that its operations remain efficient.

Imagine a library where books are organized on shelves alphabetically. If you want to find a specific book ('Catcher in the Rye'), you can quickly check the middle of the shelf. If the book is before the middle, you only need to look at the left side, and if it’s after, you look to the right. This method helps you find the book much quicker than if you had to check each title one by one.

So, a binary tree is just a tree with a root in which every node has either 1, 2 or 3 children. The heap poses a very special kind of binary tree, which we filled up top to bottom left to right, but in general a binary tree has no constraint.

In computer science, a binary tree is a data structure where each node can have at most two children, referred to as the left child and the right child. The organization of nodes in a binary tree does not follow a specific pattern — it can have any arrangement of nodes, but in a binary search tree, we impose additional constraints on how the values are organized.

Think of a family tree. Each person can have up to two children (a left and a right). However, the arrangement of people within that tree can vary widely; there is no strict rule about who must be where other than the family connections.

So, in a binary search tree, the binary tree could have an arbitrary structure that the values are arranged in a specific way. For each node with a value v, all the nodes below v, smaller than v are in the left sub tree and all the values bigger than v are in the rights sub tree.

The defining characteristic of a binary search tree is how it arranges its values. For any node with a value 'v', all values that are less than 'v' must be located in the left subtree and all values greater than 'v' are found in the right subtree. This property allows for efficient searching since you can eliminate half of the tree at each step depending on whether the value you're searching for is smaller or larger than the current node's value.

Consider a game of 'higher or lower' with numbers. You start by guessing a number and, based on whether your guess is too high or too low, you narrow down your search to either the lower half or the upper half of the possible numbers. This method reduces the number of guesses needed to find the target number.

So, the first thing that we can do with a binary search tree is to list out its values in sorted order, this is called an in order traversal.

In-order traversal is a method of visiting every node in a binary search tree where you first visit the left child, then the current node, and finally the right child. This traversal method guarantees that you will access all the nodes in ascending sorted order due to the properties of the binary search tree.

Imagine you are organizing your closet. You start by going through all items on the left side (maybe shoes), then you pause to evaluate the current item in hand (a T-shirt), and lastly, you check the items on the right side (perhaps winter jackets). By following this order, you effectively sort through your closet without missing a single item.

Now searching for a tree a value in a binary search tree is very much like binary search.

Searching for a value in a binary search tree follows a logical process similar to the binary search method used in arrays. You start at the root; if the current node's value matches the target, you've found your value. If the target is smaller, you move to the left subtree. If it’s larger, you move to the right subtree. This process continues recursively until you either find the value or conclude that it is not in the tree.

Consider looking for a word in a dictionary. You start in the middle of the book, checking if that word is before or after your current page. Based on that, you flip to the relevant half (either the beginning or the end) to continue your search. This allows you to quickly find the word without checking every single entry.

--