University of Arizona, Department of Computer Science

CSc 120: Binary Search Trees

Expected Behavior

Implement a class BinarySearchTree that behaves as specified below.

Instances of this class should satisfy the binary search tree property. Namely, for every node in the tree, the values in the left subtree should all be smaller than the value at that node; and the values in the right subtree should all be bigger than the value at that node. To create a binary search tree, begin with an empty tree and repeatedly insert values into it. The algorithm for inserting a value into a binary search tree is given in the lecture notes.

Attributes

Each node in the tree should have a value (an integer) as well as references to the left and right subtrees. The names for the attributes are up to you.

Methods

Your class should implement (at least) the following methods:

__init__(self)
Initializes a tree node to be empty. Attribute values are set to None.

add(self, val)
Adds a node with the value val to the tree so as to maintain the binary search tree property (see above).

find(self, val)
Returns: a reference to the tree node with value val if it exists, None otherwise.

__str__(self)
Returns a string representation of the tree. For the purposes of this assignment, this is defined as follows. Given a tree T:

  • If T is None (i.e., empty), return the string "None" (the quotation marks simply indicate that the value is a string; they are not part of the string itself).
  • Otherwise, suppose that T has a root node with value val and left and right subtrees Tleft and Tright. Return the string
    "({:d} {} {})".format( val, str(Tleft), str(Tright))

Gotchas to watch out for

The code shown in the class lecture notes for binary search trees are for functions, not methods for a class. This problem asks you to write methods for a class. The difference is that methods are invoked on objects; in this case, these objects are binary search trees.

This can become an issue when a recursive method reaches a node whose left and/or right subtree is empty (i.e., None). Attempting to recurse on the empty subtree will generate an error because the None object is not a tree and does not have the methods you have written for this class.

You can get around this problem by checking that you have a non-None subtree before making a recursive call. (The case where the subtree is empty will, of course, have to be dealt with appropriately.)

Examples

In each of the following examples, we construct a binary search tree by inserting the sequence of values shown (in L-to-R order),then print out the resulting tree.

Input sequence (L-to-R) str(tree)
1 2 3 (1 None (2 None (3 None None)))
2 1 3 (2 (1 None None) (3 None None))
5 3 1 2 (5 (3 (1 None (2 None None)) None) None)
4 3 2 1 5 6 (4 (3 (2 (1 None None) None) None) (5 None (6 None None)))
4 3 1 2 6 5 (4 (3 (1 None (2 None None)) None) (6 (5 None None) None))

In each of the following examples, we construct a binary search tree by inserting the sequence of values shown (in L-to-R order),then print out the tree returned by find(3).

Input sequence (L-to-R) str(tree.find(3))
1 2 3 (3 None None)
2 1 3 (3 None None)
5 3 1 2 (3 (1 None (2 None None)) None)
4 3 2 1 5 6 (3 (2 (1 None None) None) None)
4 3 1 2 6 5 (3 (1 None (2 None None)) None)