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))

Top-level functions vs methods

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.

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)