A Binary Search Tree is an efficient data structure for fast (
O(log N)) data storage and retrieval. It is a specialized tree data structure that is made up of a root node, and at most two child branches, or subtrees.
Depending on the requirements, a Binary Search Tree can have certain qualities. It can allow duplicate values to exist, or enforce that there are unique values only. If duplicate values are allowed, it must be decided whether nodes with equal value go on the root’s left subtree or right subtree.
For this implementation, duplicate values will be allowed, and nodes with values that are the same as the root node’s will be in the root node’s right subtree.
Each node will be an instance of the
BinarySearchTree class and will have the following properties:
- a value that represents the data stored
- a depth, where a depth of
1indicates the top level, or root, of the tree and a depth greater than
1is a level somewhere lower in the tree
- a left instance variable that points to a left child which is itself a Binary Search Tree, and must have a data lesser than its parent node’s data
- a right instance variable that points to a right child which is itself a Binary Search Tree, and must have a data greater than or equal to its parent node’s data
In the following exercises, we will be implementing a Binary Search Tree in Python. Each Binary Search Tree node will have the instance variables
right, and methods for insertion, retrieval, and traversal of the tree. Let’s get started!
We have provided an empty
BinarySearchTree class in BinarySearchTree.py. Remove
pass and do the following inside the class definition:
- Define an
__init__()method with the following parameters:
valueis the data contained within the binary search tree and
depthindicates the level of the tree.
- Assign a default argument value of
- Declare an instance variable,
value, and assign this to the parameter
- Declare another instance variable,
depth, and assign this to the parameter
right instance variables which will represent the left and right subtree nodes and assign each one to
BinarySearchTree instance called
root with a
15. This creates a root tree node.