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
1
indicates the top level, or root, of the tree and a depth greater than1
is 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 data
, depth
, left
and right
, and methods for insertion, retrieval, and traversal of the tree. Let’s get started!
Instructions
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:self
,value
, anddepth
wherevalue
is the data contained within the binary search tree anddepth
indicates the level of the tree. - Assign a default argument value of
1
todepth
. - Declare an instance variable,
value
, and assign this to the parametervalue
. - Declare another instance variable,
depth
, and assign this to the parameterdepth
.
Define left
and right
instance variables which will represent the left and right subtree nodes and assign each one to None
.
Instantiate a BinarySearchTree
instance called root
with a value
of 15
. This creates a root tree node.
Print root
‘s value
.