Definition

A binary search tree (BST) is a binary tree where every node in the left subtree is less than the root, and every node in the right subtree is of a value greater than the root. The properties of a binary search tree are recursive: if we consider any node as a “root,” these properties will remain true.

Due to the way nodes in a binary search tree are ordered, an in-order traversal (left node, then root node, then right node) will always produce a sequence of values in increasing numerical order.

Searching

Binary search trees are called “search trees” because they make searching for a certain value more efficient than in an unordered tree. In an ideal binary search tree, we do not have to visit every node when searching for a particular value.

Here is how we search in a binary search tree:

1. Begin at the tree’s root node

2. If the value is smaller than the current node, move left

3. If the value is larger than the current node, move right

Inserting

New nodes in a binary search tree are always added at a leaf position. Performing a search can easily find the position for a new node.

Removing

When removing from a binary search tree, we are concerned with keeping the rest of the tree in the correct order. This means removing is different depending on whether the node we are removing has children. There are three cases:

If the node being removed is a leaf, it can simply be deleted.

If the node has a single child, (left or right) we must move the child into the position of the node when deleting it.

If the node has two children, we must first find the In-Order Predecessor (IOP): the largest node in our node’s left subtree. The IOP is always a leaf node, and can be found by starting at the left subtree’s root and moving right. We can then swap the node being removed with its IOP and delete it, as it is now a leaf.

Runtime and BSTs

Depending on the values contained in a binary search tree, and the order in which they are added, the performance of a BST’s operations can vary. This performance depends on the shape of the tree and the number of nodes it contains.

In an ideal case, a binary search tree has a similar number of nodes in its right and left subtrees. Since you have to visit less nodes when searching in an ideal BST, this case has a run time of O(lg(n)) for all operations that utilize find, including search, insert, and remove.

The worst case of a binary search tree is one that has its values added in numerical order. This structure then doesn’t resemble a tree - it looks like a linked list! As potentially every node has to be visited when searching, the worst case BST has a run time of O(n) for all operations utilizing find.

Objective 01 - Describe the properties of a binary tree and the properties of a "perfect" tree

Overview

There are lots of different types of tree data structures. A binary tree is a specific type of tree. It is called a binary tree because each node in the tree can only have a maximum of two child nodes. It is common for a node's children to be called either left or right.

Here is an example of a what a class for a binary tree node might look like:

Follow Along

With this simple class, we can now build up a structure that could be visualized like so:

"Perfect" Trees

A "perfect" tree has all of its levels full. This means that there are not any missing nodes in each level.

"Perfect" trees have specific properties. First, the quantity of each level's nodes doubles as you go down.

Second, the quantity of the last level's nodes is the same as the quantity of all the other nodes plus one.

These properties are useful for understanding how to calculate the height of a tree. The height of a tree is the number of levels that it contains. Based on the properties outlined above, we can deduce that we can calculate the tree's height with the following formula:

In the formula above, n is the total number of nodes. If you know the tree's height and want to calculate the total number of nodes, you can do so with the following formula:

We can represent the relationship between a perfect binary tree's total number of nodes and its height because of the properties outlined above.

Challenge

1. Calculate how many levels a perfect binary tree has given that the total number of nodes is 127.

2. Calculate the total number of nodes on a perfect binary tree, given that the tree's height is 8.

Additional Resources

Objective 02 - Recall the time and space complexity, the strengths and weaknesses, and the common uses of a binary search tree

Overview

Just like a binary tree is a specific type of tree, a binary search tree (BST) is a specific type of binary tree. A binary search tree is just like a binary tree, except it follows specific rules about how it orders the nodes contained within it. For each node in the BST, all the nodes to the left are smaller, and all the nodes to the right of it are larger.

We can call a binary search tree balanced if the heights of its left and right subtrees differ by at most one, and both of the subtrees are also balanced.

Follow Along

Time and Space Complexity

Lookup

If a binary search tree is balanced, then a lookup operation's time complexity is logarithmic (O(log n)). If the tree is unbalanced, the time complexity can be linear (O(n)) in the worst possible case (virtually a linear chain of nodes will have all the nodes on one side of the tree).

Insert

If a binary search tree is balanced, then an insertion operation's time complexity is logarithmic (O(log n)). If the tree is entirely unbalanced, then the time complexity is linear (O(n)) in the worst case.

Delete

If a binary search tree is balanced, then a deletion operation's time complexity is logarithmic (O(log n)). If the tree is entirely unbalanced, then the time complexity is linear (O(n)) in the worst case.

Space

The space complexity of a binary search tree is linear (O(n)). Each node in the binary search tree will take up space in memory.

Strengths

One of the main strengths of a BST is that it is sorted by default. You can pull out the data in order by using an in-order traversal. BSTs also have efficient searches (O(log n)). They have the same efficiency for their searches as a sorted array; however, BSTs are faster with insertions and deletions. In the average-case, dictionaries have more efficient operations than BSTs, but a BST has more efficient operations in the worst-case.

Weaknesses

The primary weakness of a BST is that they only have efficient operations if they are balanced. The more unbalanced they are, the worse the efficiency of their operations gets. Another weakness is that they are don't have stellar efficiency in any one operation. They have good efficiency for a lot of different operations. So, they are more of a general-purpose data structure.

If you want to learn more about trees that automatically rearrange their nodes to remain balanced, look into or

Challenge

1. In your own words, explain why an unbalanced binary search tree's performance becomes degraded.

Additional Resources

Objective 03 - Construct a binary search tree that can perform basic operations with a logarithmic time complexity

Overview

To create a binary search tree, we need to define two different classes: one for the nodes that will make up the binary search tree and another for the tree itself.

Follow Along

Let's start by creating a BSTNode class. An instance of BSTNode should have a value, a right node, and a left node.

Now that we have our basic BSTNode class defined with an initialization method let's define our BST class. This class will have an initialization method and an insert method.

Notice that our BST class expects each BSTNode to have an insert method available on an instance object. But, we haven't yet added an insert method on the BSTNode class. Let's do that now.

Now that we can insert nodes into our binary search tree let's define a search method that can lookup values in our binary search tree.

Our BST class expects there to be a search method available on the BSTNode instance stored at the root. Let's go ahead and define that now.

Challenge

To implement a delete operation on our BST and BSTNode classes, we must consider three cases:

1. If the BSTNode to be deleted is a leaf (has no children), we can remove that node from the tree.

2. If the BSTNode to be deleted has only one child, we copy the child node to be deleted and delete it.

3. If the BSTNode

Given the above information, can you write pseudocode for a method that can find the minimum value of all the nodes within a tree or subtree?

Additional Resources