How to Implement a Binary Search Tree (BST) in Python

To implement a Binary Search Tree (BST) in Python, define a Node class with value, left, and right attributes, then create a BST class with methods to insert and search nodes. The tree keeps values ordered so that left children are smaller and right children are larger than the parent node.

Syntax

The BST implementation involves two main parts: a Node class to represent each tree node, and a BST class to manage the tree operations.

• Node holds a value and pointers to left and right child nodes.
• BST has methods like insert to add values and search to find values.

python

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

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

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

    def _insert_recursive(self, current_node, value):
        if value < current_node.value:
            if current_node.left is None:
                current_node.left = Node(value)
            else:
                self._insert_recursive(current_node.left, value)
        else:
            if current_node.right is None:
                current_node.right = Node(value)
            else:
                self._insert_recursive(current_node.right, value)

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

    def _search_recursive(self, current_node, value):
        if current_node is None:
            return False
        if value == current_node.value:
            return True
        elif value < current_node.value:
            return self._search_recursive(current_node.left, value)
        else:
            return self._search_recursive(current_node.right, value)

Example

This example shows how to create a BST, insert values, and search for values in the tree.

python

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

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

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

    def _insert_recursive(self, current_node, value):
        if value < current_node.value:
            if current_node.left is None:
                current_node.left = Node(value)
            else:
                self._insert_recursive(current_node.left, value)
        else:
            if current_node.right is None:
                current_node.right = Node(value)
            else:
                self._insert_recursive(current_node.right, value)

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

    def _search_recursive(self, current_node, value):
        if current_node is None:
            return False
        if value == current_node.value:
            return True
        elif value < current_node.value:
            return self._search_recursive(current_node.left, value)
        else:
            return self._search_recursive(current_node.right, value)

# Create BST and insert values
bst = BST()
bst.insert(10)
bst.insert(5)
bst.insert(15)
bst.insert(3)
bst.insert(7)

# Search for values
print(bst.search(7))  # True
print(bst.search(8))  # False

Output

True
False

Common Pitfalls

Common mistakes when implementing a BST include:

• Not handling the case when the tree is empty before inserting.
• Inserting duplicate values without a clear rule (usually duplicates go to the right or are ignored).
• Forgetting to recurse properly when inserting or searching.
• Mixing up left and right child comparisons.

Always test edge cases like empty trees and searching for non-existent values.

python

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

    def insert(self, value):
        # Wrong: does not handle empty tree
        if self.root is None:
            self.root = Node(value)
        else:
            self._insert_recursive(self.root, value)

    def _insert_recursive(self, current_node, value):
        if value < current_node.value:
            if current_node.left is None:
                current_node.left = Node(value)
            else:
                self._insert_recursive(current_node.left, value)
        else:
            if current_node.right is None:
                current_node.right = Node(value)
            else:
                self._insert_recursive(current_node.right, value)

# Correct way is to check if root is None before inserting, as shown in the previous example.

Quick Reference

• Node class: stores value and left/right children.
• Insert method: adds values maintaining BST order.
• Search method: finds if a value exists in the tree.
• Left child: smaller values.
• Right child: larger values.

Key Takeaways

Define a Node class with value, left, and right attributes to represent tree nodes.

Use recursive insert and search methods in the BST class to maintain order and find values.

Always check if the tree root is None before inserting the first node.

Remember left children hold smaller values and right children hold larger values.

Test your BST with edge cases like empty trees and searching for missing values.