Definition of Binary Search Trees

BST (Binary Search Trees) are a type of user-defined data structure used for hierarchically storing data, each Node of BSTs store data and have two children; The left child stores an item that is smaller than the item stored in the Node, and the right child stores an item that is greater than the item stored in the Node. This structure allows for a more efficient way of storing the data as the insertion, searching and deletion will have a lesser number of elements to look at rather than looking at all the elements of the tree.

Implementation of Binary Trees in python

First, let's create a class that defines the Node :

class Node:
    def __init__(self, value):
        self.value = value
        self.right_node = None
        self.left_node = None

This class has 3 attributes, the value which is the element of the node, the right node and the left node which are the children of the current node. Note that the right node and left node are nodes too.

Now, let's create the BST class:

# Create the binary search tree
class BinarySearchTree:
    def __init__(self):
        self.root = None

This class has an attribute called root which is by default None. Then, let's define a function to insert values recursively in our binary search tree:

    def insert(self, value):
        if self.root == None:
            self.root = Node(value)
        else:
            self._insert(value, self.root)

    def _insert(self, value, cur_node):
        if value < cur_node.value:
            if cur_node.left_node == None:
                cur_node.left_node = Node(value)
            else:
                self._insert(value, cur_node.left_node)
        elif value > cur_node.value:
            if cur_node.right_node == None:
                cur_node.right_node = Node(value)
            else:
                self._insert(value, cur_node.right_node)
        else:
            print("Value Already In Tree!")

Here, we have defined two methods: insert() and _insert(). insert() is a public method that takes the value to be stored as a parameter. It first checks if the root node is None and, if so, it inserts the value in the root node. However, if the tree is not empty, the method calls the private method _insert() to insert the value in the appropriate node.

_insert() is a recursive function that takes two parameters: the value to be inserted and the current node. It compares the value to be inserted with the value of the current node. If the value is less than the current node's value, it checks if the left node is empty and, if so, inserts the value in the left node. Otherwise, it calls _insert() again on the left node. If the value is greater than the current node's value, it checks if the right node is empty and, if so, inserts the value in the right node. If the value is equal to the current node's value, it prints a message indicating that the value already exists in the tree.

Now, let's recursively print the tree to show the elements in an ordered way :

    # Print the tree in order
    def print_tree(self):
        if self.root != None:
            self._print_tree(self.root)

    def _print_tree(self, cur_node):
        if cur_node != None:
            self._print_tree(cur_node.left_node)
            print(f"{cur_node} : {cur_node.value}")
            self._print_tree(cur_node.right_node)

Conclusion

In conclusion, Binary Search Trees (BSTs) are a hierarchical data structure used for efficient storage, searching, and retrieval of data. They store data in nodes where each node has two children, a left child, and a right child, with the left child storing an item smaller than the current node's value and the right child storing an item greater than the current node's value.

Bonus!

Subscribe to my newsletter now and receive free courses, valuable tips, and cheat sheets in PDF format! Stay up-to-date with the latest news and trends in your field and gain access to exclusive content only available to subscribers. Join our community today and start learning for free!

Thank you for reading, and let's connect! 🤝

Thank you for reading my blog. Feel free to subscribe to my email newsletter and connect on Twitter
If you like this article! Don't miss the upcoming ones, follow me and subscribe to my newsletter to receive more!
See you soon :)