Python: Binary Search Tree Implementation

1. Introduction

A Binary Search Tree (BST) is a binary tree where each node has a value, and the left subtree of a node contains only nodes with values less than the node's value, and the right subtree only nodes with values greater than the node's value. This provides an efficient way to store data that allows for fast retrieval, insertion, and deletion operations.

2. Program Overview

In this program, we will:

1. Define a class Node to represent individual nodes of the BST.

2. Define a class BinarySearchTree which will contain methods for inserting, searching, and traversing the BST.

3. Code Program

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

class BinarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self, key):
        if self.root is None:
            self.root = Node(key)
        else:
            self._insert_recursive(self.root, key)

    def _insert_recursive(self, node, key):
        if key < node.val:
            if node.left is None:
                node.left = Node(key)
            else:
                self._insert_recursive(node.left, key)
        else:
            if node.right is None:
                node.right = Node(key)
            else:
                self._insert_recursive(node.right, key)

    def search(self, key):
        return self._search_recursive(self.root, key)

    def _search_recursive(self, node, key):
        if node is None:
            return False
        if key == node.val:
            return True
        if key < node.val:
            return self._search_recursive(node.left, key)
        return self._search_recursive(node.right, key)

    def inorder_traversal(self, node, result=None):
        if result is None:
            result = []
        if node:
            self.inorder_traversal(node.left, result)
            result.append(node.val)
            self.inorder_traversal(node.right, result)
        return result


# Demonstration
tree = BinarySearchTree()
tree.insert(50)
tree.insert(30)
tree.insert(20)
tree.insert(40)
tree.insert(70)
tree.insert(60)
tree.insert(80)

# Inorder traversal
print(tree.inorder_traversal(tree.root))

# Search in BST
print(tree.search(25))
print(tree.search(70))

Output:

[20, 30, 40, 50, 60, 70, 80]
False
True

4. Step By Step Explanation

1. The Node class is designed to initialize and represent individual nodes in our BST.

2. The BinarySearchTree class is used to perform operations on the BST.

3. Within BinarySearchTree, the insert method will add a new value to our BST.

- If the tree is empty, a new node becomes the root.- If the tree is not empty, _insert_recursive decides where the new node should go.

4. The search method allows us to determine if a value exists within our BST.

5. _search_recursive aids in this search, traversing the tree as needed based on comparisons.

6. inorder_traversal is a helper method that provides us a way to traverse and print the entire BST. This kind of traversal ensures the values are printed in ascending order.