# Sample Video Frame

# Exercise 20: Binary Search Trees

In this exercise I'm going to teach you to translate an English description of a data structure into working code. You already know how to analyze the code for an algorithm or data structure using the master copy method. You also know how to read a p-code (psuedo-code) description of an algorithm. Now you will combine the two and learn how to break down a rather loose English description of the Binary Search Tree.

I'm going to start off right away and warn you to *not* visit the Wikipedia page when you do this exercise. The Binary Search Tree description on Wikipedia has mostly working Python code for the data structure, so it would defeat the point of this exercise. If you get stuck then you'll be able to read any resources you can, but first try to do it from just my descriptions here.

## Binary Search Trees

In Exercise 16 you saw how a Merge Sort takes a flat, linked list and seems to convert it into a tree of sorted parts. It keeps cutting the list into smaller pieces and then assembles the pieces back together by sorting lesser valued parts on the "left" and greater valued parts on the right. In a way, a Binary Search Tree (`BSTree`

) is a data structure that does this sorting right away and never tries to keep the items in a list. The main usage for a `BSTree`

is to use a tree to organize pairs of `key=value`

nodes in order *ahead* of time, as you insert or delete them.

A `BSTree`

does this by starting the tree at a root `key=value`

, and having a right or left path (link). If you insert a new `key=value`

, then the `BSTree`

's job is to start at the root and compare the `key`

to each node: going left if your new key is less-than and going right if your key is greater-than. Eventually the `BSTree`

finds a position in the tree that--should you follow the original path--will find it by following the same process. All operations after that do the same thing by comparing any keys to each node, moving left and right until it either finds the node or reaches a dead end.

In this way a `BSTree`

is an alternative to a `Dictionary`

from Exercise 17, and so it should have the same operations. The basic `BSTreeNode`

would need `left`

, `right`

, `key`

, and `value`

attributes to create the tree structure. You may also need a `parent`

attribute depending on how you do this. The `BSTree`

then needs the following operations on a `root`

`BSTreeNode`

:

- get: Given a
`key`

, walk the tree to find the node, or return`None`

if you reach a dead end. You go`left`

if the given`key`

is less-than the node's`key`

. You go right if the`key`

is greater-than the node's`key`

. If you read a node with no left or right, then you're done and the node does not exist. There is a way to do this using recursion and using a while loop. - set: This is nearly the same as
`get`

except once you reach that dead end node you simply attach a new`BSTreeNode`

on the`left`

or`right`

, thus extending the tree down one more branch. - delete: Deleting nodes from a BSTree is a complex operation, so I have a whole section just on delete. The short version is you have three conditions: Deleting nodes from a
`BSTree`

is a complex operation, so I have a whole section just on`delete`

. The short version is you have three conditions: the node is a leaf (no children), has one child, or has two children. If it's a leaf then just remove it. If it has one child, then replace it with the child. If it has two children, then it gets really complicated so read the section on deleting below. - list: Walk the tree and print everything out. The important piece to
`list`

is that you can walk the tree in different ways to produce different output. If you walk the`left`

, then the`right`

paths, you get something different than if you do the inverse. If you go all the way to the bottom and then print as you come up the tree toward`root`

, you get yet another kind of output. You can also print the nodes as you go down the tree, from`root`

to the "leaves". Try different styles to see which one does what.

## Register for Learn More Python the Hard Way

Register today for the course and get the all currently available videos and lessons, plus all future modules for no extra charge.