Binary Search Tree Implementation in Python

← Back to Data Structures and Algorithms in Python

1. Introduction

A Binary Search Tree (BST) is a specialized version of a binary tree where for each node, all elements in the left subtree are less than the node, and all elements in the right subtree are greater than the node. It provides the advantage of faster search, insert, and delete operations compared to linear data structures like arrays and linked lists.

2. Implementation Steps

1. Define a Node class that will contain data, a left child, and a right child.

2. Implement the BinarySearchTree class which initializes the root node.

3. Provide methods to insert, search, delete, and display the tree using inorder traversal.

3. Implementation in Python

class Node:
    def __init__(self, data):
        self.data = data  # Holds the data for the node
        self.left = None  # Pointer to the left child node
        self.right = None  # Pointer to the right child node
class BinarySearchTree:
    def __init__(self):
        self.root = None  # Initialize the root of the tree as None
    def insert(self, data):
        # Insert data into the tree
        if self.root is None:
            self.root = Node(data)
        else:
            self._insert_recursive(self.root, data)
    def _insert_recursive(self, node, data):
        # A private helper function to insert data recursively
        if data < node.data:
            if node.left is None:
                node.left = Node(data)
            else:
                self._insert_recursive(node.left, data)
        elif data > node.data:
            if node.right is None:
                node.right = Node(data)
            else:
                self._insert_recursive(node.right, data)
    def search(self, data):
        # Search for data in the tree
        return self._search_recursive(self.root, data)
    def _search_recursive(self, node, data):
        # A private helper function to search for data recursively
        if node is None:
            return False
        if node.data == data:
            return True
        if data < node.data:
            return self._search_recursive(node.left, data)
        return self._search_recursive(node.right, data)
    def inorder(self):
        # Display tree using inorder traversal
        return self._inorder_recursive(self.root)
    def _inorder_recursive(self, node):
        # A private helper function for inorder traversal
        result = []
        if node:
            result += self._inorder_recursive(node.left)
            result.append(node.data)
            result += self._inorder_recursive(node.right)
        return result
# Test the BinarySearchTree class
bst = BinarySearchTree()
bst.insert(50)
bst.insert(30)
bst.insert(70)
bst.insert(20)
bst.insert(40)
print("Inorder traversal:", bst.inorder())
print("Search for 40:", bst.search(40))
print("Search for 80:", bst.search(80))

Output:

Inorder traversal: [20, 30, 40, 50, 70]
Search for 40: True
Search for 80: False

Explanation:

1. The Node class is designed to hold its data, a left child, and a right child.

2. The BinarySearchTree class starts with a root which is the initial node of the tree.

3. The insert method adds data to the tree. If the tree is empty, the root node is established. If not, a recursive helper function (_insert_recursive) finds the correct position for the new node.

4. The search method checks whether a specific data value exists in the tree. It uses a recursive function (_search_recursive) to complete the search.

5. The inorder method showcases the tree using the inorder traversal technique. This outputs a sorted sequence for binary search trees.

6. In the testing segment, we initiate a binary search tree, inject several values, and then conduct search and display functions.

Related Data Structures in Python


Comments

Post a Comment