How to implement a binary search tree in Python?

Question

Jayant Kumar · Accepted Answer

Table of Contents
Introduction
A Binary Search Tree (BST) is a node-based data structure that allows efficient searching, insertion, and deletion of elements. This makes it a popular choice for sorted data management. In Python, implementing a BST involves defining a Node class and a BinarySearchTree class that manages the tree operations.
1. Structure of a Binary Search Tree
A BST consists of nodes where:

Each node contains a value.
The left child of a node contains values smaller than the parent node.
The right child contains values greater than the parent node.
This recursive structure ensures efficient search and insertion operations.

2. Implementing a Binary Search Tree in Python
Step : Define the Node Class
Each node in the tree holds a value, and pointers to its left and right children. Here's the code to create the Node class.
class Node:
    def __init__(self, key):
        self.value = key
        self.left = None
        self.right = None

Step : Define the BinarySearchTree Class
The BinarySearchTree class will contain methods for insertion, searching, and traversal of the tree.
class BinarySearchTree:
    def __init__(self):
        self.root = None

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

# Recursive insertion helper method
    def _insert_recursive(self, current_node, key):
        if key &#x3C; current_node.value:
            if current_node.left is None:
                current_node.left = Node(key)
            else:
                self._insert_recursive(current_node.left, key)
        else:
            if current_node.right is None:
                current_node.right = Node(key)
            else:
                self._insert_recursive(current_node.right, key)

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

# Recursive search helper method
    def _search_recursive(self, current_node, key):
        if current_node is None or current_node.value == key:
            return current_node
        if key &#x3C; current_node.value:
            return self._search_recursive(current_node.left, key)
        return self._search_recursive(current_node.right, key)

# In-order traversal (left-root-right)
    def in_order_traversal(self, node):
        if node is not None:
            self.in_order_traversal(node.left)
            print(node.value, end=' ')
            self.in_order_traversal(node.right)

3. Operations in the Binary Search Tree
Insertion in a BST
Insertion starts by comparing the value to be inserted with the root node. If the value is smaller, it is inserted in the left subtree; otherwise, in the right subtree.
# Example usage
bst = BinarySearchTree()
bst.insert(50)
bst.insert(30)
bst.insert(20)
bst.insert(40)
bst.insert(70)
bst.insert(60)
bst.insert(80)

print("In-order Traversal:")
bst.in_order_traversal(bst.root)  # Output: 20 30 40 50 60 70 80

Searching in a BST
Searching works by recursively checking the left or right subtree based on comparisons with the node's value.
# Search for a value in the BST
found_node = bst.search(40)
if found_node:
    print(f"
Node with value {found_node.value} found.")  # Output: Node with value 40 found.
else:
    print("
Node not found.")

In-order Traversal
In-order traversal visits nodes in ascending order (left subtree -> root -> right subtree).
# In-order traversal prints: 20 30 40 50 60 70 80

Conclusion
Implementing a Binary Search Tree in Python provides an efficient way to handle sorted data. The BST structure allows for quick search, insertion, and traversal operations. By following this guide, you can easily create your own BST in Python and apply it to various scenarios like data indexing or range queries.

How to implement a binary search tree in Python?

Table of Contents

Introduction

1. Structure of a Binary Search Tree

2. Implementing a Binary Search Tree in Python

Step : Define the `Node` Class

Step : Define the `BinarySearchTree` Class

3. Operations in the Binary Search Tree

Insertion in a BST

Searching in a BST

In-order Traversal

Conclusion

Similar Questions