Binary Search Tree In Python

A Binary Search Tree (BST) is a type of binary tree where the left child node’s value is smaller than its parent node, and the right child node’s value is greater than its parent node. This property makes searching for values in the tree more efficient, typically O(log n) for balanced trees.

Here is an implementation of a simple Binary Search Tree in Python:

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


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

    # Insert a node into the tree
    def insert(self, root, key):
        if root is None:
            return Node(key)
        
        if key < root.value:
            root.left = self.insert(root.left, key)
        else:
            root.right = self.insert(root.right, key)

        return root

    # In-order traversal (left, root, right)
    def inorder(self, root):
        if root:
            self.inorder(root.left)
            print(root.value, end=" ")
            self.inorder(root.right)

    # Search for a value in the tree
    def search(self, root, key):
        # Base case: root is null or key is present at the root
        if root is None or root.value == key:
            return root

        # Key is greater than root's value
        if key > root.value:
            return self.search(root.right, key)

        # Key is smaller than root's value
        return self.search(root.left, key)

    # Wrapper function for insert
    def insert_value(self, key):
        self.root = self.insert(self.root, key)

    # Wrapper function for inorder traversal
    def inorder_traversal(self):
        self.inorder(self.root)
        print()  # for a new line after traversal

    # Wrapper function for search
    def search_value(self, key):
        result = self.search(self.root, key)
        if result:
            print(f"Node {key} found in the tree.")
        else:
            print(f"Node {key} not found in the tree.")


# Example usage
bst = BinarySearchTree()
bst.insert_value(50)
bst.insert_value(30)
bst.insert_value(20)
bst.insert_value(40)
bst.insert_value(70)
bst.insert_value(60)
bst.insert_value(80)

# In-order traversal of BST
print("In-order traversal of the BST:")
bst.inorder_traversal()

# Search for values
bst.search_value(40)
bst.search_value(90)

Explanation:

1. Node class: Represents a single node in the BST with properties left, right, and value.
2. BinarySearchTree class: Contains the root and methods for insertion, search, and in-order traversal.
   • insert: Recursively finds the correct position for a new value.
   • inorder: Prints the nodes in ascending order.
   • search: Searches for a value in the tree by comparing it with the root node and moving left or right based on the comparison.

Example Output:

In-order traversal of the BST:
20 30 40 50 60 70 80
Node 40 found in the tree.
Node 90 not found in the tree.

This is a simple implementation of a Binary Search Tree. You can extend it with additional functionalities like deletion, balancing, or finding the minimum/maximum nodes.