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 than1is 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, anddepthwherevalueis the data contained within the binary search tree anddepthindicates the level of the tree. - Assign a default argument value of
1todepth. - 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.