Python Object-Oriented Programming: Binary search tree class with insertion and search methods

Last update on December 21 2024 07:40:32 (UTC/GMT +8 hours)

Binary search tree:

In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left subtree and less than the ones in its right subtree. The time complexity of operations on the binary search tree is directly proportional to the height of the tree.

Visual Presentation:

Write a Python program to create a class representing a binary search tree. Include methods for inserting and searching for elements in the binary tree.

Sample Solution:

Python Code:

# Define a class called Node to represent a node in a binary search tree (BST)
class Node:
    # Initialize the Node object with a value, and set the left and right child pointers to None
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

    # Define a custom __str__ method to convert the node's value to a string
    def __str__(self):
        return str(self.value)

# Define a class called BinarySearchTree to represent a binary search tree
class BinarySearchTree:
    # Initialize the BST with an empty root node
    def __init__(self):
        self.root = None

    # Insert a value into the BST
    def insert(self, value):
        # If the root is None, create a new node with the given value as the root
        if self.root is None:
            self.root = Node(value)
        else:
            self._insert_recursive(self.root, value)

    # Helper method to recursively insert a value into the BST
    def _insert_recursive(self, node, value):
        if value < node.value:
            if node.left is None:
                node.left = Node(value)
            else:
                self._insert_recursive(node.left, value)
        elif value > node.value:
            if node.right is None:
                node.right = Node(value)
            else:
                self._insert_recursive(node.right, value)

    # Search for a value in the BST
    def search(self, value):
        return self._search_recursive(self.root, value)

    # Helper method to recursively search for a value in the BST and return the node if found
    def _search_recursive(self, node, value):
        if node is None or node.value == value:
            return node
        if value < node.value:
            return self._search_recursive(node.left, value)
        else:
            return self._search_recursive(node.right, value)

# Example usage
# Create an instance of BinarySearchTree
bst = BinarySearchTree()

# Insert values into the BST
bst.insert(5)
bst.insert(3)
bst.insert(7)
bst.insert(2)
bst.insert(4)
bst.insert(6)
bst.insert(8)

# Search for elements in the BST and print the results
print("Searching for elements:")
print(bst.search(4))  # Found, returns the node (4)
print(bst.search(9))  # Not found, returns None 

Sample Output:

Searching for elements:
4
None

Explanation:

In this above exercise-

• We define a Node class representing a node in the binary search tree. Each node contains a value, as well as references to its left and right child nodes.
• The BinarySearchTree class represents the binary search tree itself. It has a root attribute that points to the root node of the tree.
• The "insert()" method inserts a new value into the tree. If the tree is empty (root is None), it creates a new node and sets it as the root. Otherwise, it calls the insertrecursive method to recursively traverse the tree and find the appropriate position to insert the new value.
• The "insertrecursive()" method compares the value to be inserted with the current node's value and decides whether to go left or right in the tree. If the left or right child is None, it creates a new node and sets it as the child. Otherwise, it continues the recursive insertion process.
• The "search()" method searches for a given value in the tree. It calls the "searchrecursive()" method to recursively traverse the tree and look for the value. If the value is found, it returns the corresponding node. If the value is not found or the tree is empty, it returns None.
• In the example usage section, we create a BinarySearchTree instance called bst. The "insert ()" method inserts several elements into the tree. We then use the search method to find specific elements and print the results.
• In the example code, when we call print(bst.search(4)), it returns a Node object that represents the node containing the value 4 in the binary search tree. Since there is no custom str method defined for the Node class, the default string representation is displayed.

Flowchart:

Python Code Editor:

Have another way to solve this solution? Contribute your code (and comments) through Disqus.

Previous: Shape class with area and perimeter calculation.
Next: Stack class with push and pop methods.