In this lesson, you have successfully built a Binary Search Tree (BST) data structure in Python. You have implemented:
- a
BinarySearchTree
class containingvalue
,depth
, andleft
andright
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 isO(logN)
for a balanced tree - if there areN
nodes in the BST, the max depth of a balanced tree islog(N)
. So, this method makes at mostlog(N)
value comparisons. In the worst case of an imbalanced tree (all values on one side), the performance would beO(N)
. - a
.get_node_by_value()
method to retrieve a node in the tree by its value. The time efficiency of this operation is alsoO(logN)
for a balanced tree - if there areN
nodes in the BST, the max depth of the tree islog(N)
, so this method makes at mostlog(N)
value comparisons. In the worst case of an imbalanced tree (all values on one side), the performance would beO(N)
. - a
.depth_first_traversal()
method to print the inorder traversal of the Binary Search Tree. This visits every single node, so if there areN
nodes, the time efficiency for traversal isO(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.