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

Sample Binary Tree

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!



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.

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.

Sign up to start coding

Mini Info Outline Icon
By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.

Or sign up using:

Already have an account?