Learn

In this lesson, you have successfully built a Binary Search Tree (BST) data structure in Python. You have implemented:

  • a BinarySearchTree class containing value, depth, and left and right child nodes.
  • an .insert() method to place a node of a specified value at the correct location in the Binary Search Tree. The time efficiency of this operation is O(logN) for a balanced tree - if there are N nodes in the BST, the max depth of a balanced tree is log(N). So, this method makes at most log(N) value comparisons. In the worst case of an imbalanced tree (all values on one side), the performance would be O(N).
  • a .get_node_by_value() method to retrieve a node in the tree by its value. The time efficiency of this operation is also O(logN) for a balanced tree - if there are N nodes in the BST, the max depth of the tree is log(N), so this method makes at most log(N) value comparisons. In the worst case of an imbalanced tree (all values on one side), the performance would be O(N).
  • a .depth_first_traversal() method to print the inorder traversal of the Binary Search Tree. This visits every single node, so if there are N nodes, the time efficiency for traversal is O(N).

Great job! The Binary Search Tree is a dynamic data structure that provides efficient insertion and searching of data. It has the benefit of being easily expandable while maintaining a sorted order of the data. In more complex implementations, we could include:

  • a .delete() method
  • a self-balancing feature as data is inserted that maintains that two sides of the tree are even, guaranteeing a max depth of log(N)

Try these out for yourself if you are up for the challenge!

Instructions

Let’s review by verifying the correctness of our implementation.

The code provided generates ten random values that are added to the Binary Search Tree with a root value of 15.

Run the file multiple times. After each run, verify that the nodes are in the right places by paying attention to the outputs from the inorder traversal of the trees. To print the inorder traversal, uncomment the last two lines of code.

Sign up to start coding

By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.
Already have an account?