Building a Binary Search Tree with datastructpy: A Journey into Data Structures

To use datastructpy in a project:

import datastructpy
from datastructpy.non_linear.trees.binary_search_tree import BinarySearchTree
print(datastructpy.__version__)

0.1.0

Hi! Welcome to this hands-on tutorial, where we will explore how to use the datastructpy package to build and manipulate a Binary Search Tree (BST). Whether you’re preparing for doing a review for a coding interview, solving a leetcode problem, or it is your first time learning about data structures, this guide will definitely help you!

The Adventure Begins: Creating a Binary Search Tree

Imagine you’re going for an epic treasure hunt in a deserted island with hidden treasures and secret paths. You found this magical map that isn’t a regular map, but a Binary Search Tree (BST) map! This map is going to be a powerful tool that will guide you to your treasure. Each point on the map is going to be a node that determines the path you take.

In this guide, you will follow the steps of the hunt as you create, explore, and manipulate the BST to discover hidden treasures (keys). We hope that along the way, you’ll learn how a Binary Search Tree works and how to use the datastructpy package to manage your map and reach your goal.

Building the Treasure Map (Building Your Tree)

The first instruction on the map is to insert some random numbers, at first, you don’t know why but the map just asks you to insert these numbers. To start our journey, we’ll create our first BST from a list of numbers. You can use the list_to_tree() function to convert a list into a Binary Search Tree:

# List of random treasures (numbers)
treasures = [10, 5, 15, 8]

# Create a Binary Search Tree from the list
bst = BinarySearchTree.list_to_tree(treasures)

# Check the structure of the tree
print("Tree Structure After Creation:")
print(bst.root.key)             # Output: 10
print(bst.root.left.key)        # Output: 5
print(bst.root.right.key)       # Output: 15
print(bst.root.left.right.key)  # Output: 8

Tree Structure After Creation:
10
5
15
8

The Treasure Hunt: Inserting New Keys

Apparently, there are other pirates that have the same map with you! You discovered that you can enter some random fake treasures to fool these other pirates.

# Insert a random fake treasure 2 to fool other pirates
bst.insert(2)

# Check if the fake treasure is added to the map
if bst.search(2):
    print("2 has been added to the map!")
else:
    print("2 was not added to the map.")

2 has been added to the map!

The Search for Lost Keys: Searching in the BST

The magical map suddenly gives you the treasure key! It is the number 12 … but is it really a hidden treasure, or just a decoy left behind by other pirates? To find out, we need to search for this key in our Binary Search Tree.

Let’s use the search method to locate this key in our BST.

# Searching for the lost treasure key (12)
search_result = bst.search(12)

# Check if the key is found
if search_result:
    print(f"The treasure key {search_result.key} was found in the BST! 🏴‍☠️")
else:
    print("The key was not found... Perhaps it was a decoy? 🤔")

The key was not found... Perhaps it was a decoy? 🤔

Overcoming Challenges: Deleting Keys from the BST

Since you found that it is a real treasure, you want to take the treasure home with you! But there is a catch, to take the treasure, you need to delete it from the map.

Step 4: Deleting Keys

# Removing a treasure from the map
bst.delete(5)

# Check if 5 is still on the map
print(bst.search(5) is not None)

False

The treasure number 5 is gone now!

The Final Structure: The Completed Tree

After a long journey, ofcourse you want to look back at the treasure hunt journey!

By now, your tree has undergone a series of transformations, and you can see how each operation (insert, search, delete) has shaped its structure. Here’s the final state of the tree:

# Final structure of the tree
print("Final Tree Structure:")
print(bst.root.key)             # Output: 15
print(bst.root.left.key)        # Output: 8

Final Tree Structure:
10
8

Your tree is now a balanced BST, with 15 as the root, 8 as the left child, and 12 as the left child of 15. It’s an efficient structure, allowing for fast insertion, search, and deletion operations.

Conclusion

Congratulations! You’ve just navigated the journey of creating, inserting, searching, and deleting nodes in a Binary Search Tree using the datastructpy package. With each step, you’ve gained a deeper understanding of how BSTs work and how to manipulate them programmatically.

The datastructpy package is an excellent tool for mastering data structures like BSTs. It provides clear, easy-to-understand implementations and is a perfect fit for learning, technical interviews, and educational projects. If you’re looking for more customization, exploration, or efficiency in your tree-based adventures, datastructpy has everything you need.

Happy coding, and may your data structures always be balanced!