High School Computer Science and Programming Workshop
Class 8: Binary Search Trees


Hesam Samimi, Cliff Kushler
Ananda Living Wisdom School



Here is a direct link to Snap!


To play with Snap! you can just click on the play button on some of the images, like the one above. If you have any problems with it loading, visit Snap! directly in a new browser tab (On that page, click "Run Snap! now"). Another possible solution, if your browser is not Chrome, is to give Chrome a try.


Trees

Today we are going to learn about a new kind of a data structure called a Binary Search Tree. In Computer Science, a tree looks like a real-life tree, except upside down:

In the tree above, each colored shape represents a node in the tree. The top node is called the root node. Each node can have one or more children, to which it connects to in the level below via links. A node at the bottom of the tree has no children, and is called a leaf. The children of a node plus all nodes connected to them are called the descendants or subtree of that node.

Note that links can only connect a parent node to its children node. For example, there cannot be link between two siblings (children of the same parent).

Typically, each node in the tree holds a value. Therefore a tree is similar to a list or set, which contain a collection of values.

Operations

Unlike a list, where we can directly access any item at any index in the list, we cannot directly access any node of the tree. The only node we get direct access to is the root. From the root then we can access one of the children, and so on, following the links.

Just like most other collection type data structures, we work with trees using operations insert (to add a new value), remove (remove a value if exists), and contains (check if a value exists).

Usage

Typically trees are used for storing hierarchical data. For example, you might have noticed that folders on your computer are stored as a (sideways) tree, with the root on the left:

Another example is a web page's source code (called HTML), which is stored as a tree:


Binary Search Trees

A Binary Tree is a tree whose nodes can have at most 2 children. Here is an example of a binary tree which holds numeric values:

A Binary Search Tree (BST) is a special type of a binary tree, whose nodes observe the following property:

The tree shown above is indeed a BST.

Usage

BSTs are used to store a collection of values just like sets. Can you guess how a BST might be more useful than a set, to store a bunch of values?

That's a tough one to guess! It turns out, because the way the values are stored, it is quicker to look up if a value is contained in the tree or not. That is, the contains operator is faster. Can you guess how?

Let's say we like to know if the tree shown above contains the value 9:

Now we can go check the left subtree and right subtree, looking for 9. But do we need to check the left subtree? No, because we are guaranteed than all their values will be equal to or less than 8. That saves us potentially looking at half of the tree!

Again, we don't need to look at the right subtree, since they will all have values greater or equal to 10.

In fact, sometimes a Set data structure is internally implemented as a BST, in cases where it is important for the contains operation to run as fast as possible.

Question: What do you suppose can be the down side of using a BST to store a set of values?

While it might be faster to look something up, it is slower to insert or remove a value! That is because you need to find the right placement for the new value, which obeys the property of the BSTs.

Brainstorming: What Is the Algorithm for Inserting a New Node?

An algorithm is a recipe---a set of concrete steps to accomplish a certain goal.

Can you discover a simple algorithm for inserting a new node intro an existing BST? As an example, say we want to add a new node of value 11 to the BST appearing above...


Exercise: Fix This BST!

Check out this program below. We have can add nodes to the BST by clicking the big green button. But oh no! It's not adding the nodes in the right places! It is not respecting the property of the Binary Search Trees.

Fortunately, there is a lot of things it is doing right though! For example, see that when you click on each node, it tells you the value of its left and right children, if it has any. Can you fix the program?

Here is a direct link to this exercise.


Next: Class 9: Values, Types, Dictionaries
Previous: Class 7: Functions
Back to: Table of Contents