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 than`1`

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

**1.**

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`

, and`depth`

where`value`

is the data contained within the binary search tree and`depth`

indicates the level of the tree. - Assign a default argument value of
`1`

to`depth`

. - Declare an instance variable,
`value`

, and assign this to the parameter`value`

. - Declare another instance variable,
`depth`

, and assign this to the parameter`depth`

.

**2.**

Define `left`

and `right`

instance variables which will represent the left and right subtree nodes and assign each one to `None`

.

**3.**

Instantiate a `BinarySearchTree`

instance called `root`

with a `value`

of `15`

. This creates a root tree node.

**4.**

Print `root`

‘s `value`

.