Python Program For Binary Search Tree (Insert, Search, Delete, Min, Max…)

In this tutorial, you will learn about the python program for binary search tree.

Binary search trees are an essential data structure in computer science and are commonly used to store and retrieve data efficiently.

In this tutorial, we will walk you through a Python program for creating and manipulating binary search trees.

We will cover the fundamental concepts, provide code examples, and address common questions related to binary search trees.

A binary search tree (BST) is a hierarchical data structure that allows efficient insertion, deletion, and search operations.

It is a type of binary tree in which each node has at most two children, referred to as the left child and the right child.

The BST property ensures that the values in the left subtree of a node are less than the node’s value, and the values in the right subtree are greater than the node’s value.

How Does a Binary Search Tree Work?

A binary search tree works based on the principle of divide and conquer.

The tree is constructed in such a way that each node serves as the root of a subtree, with all the values in the left subtree being smaller and all the values in the right subtree being larger than the node’s value.

This property allows for efficient searching, insertion, and deletion operations.

Here is a Python program that implements a binary search tree.

This program provides functions for creating a BST, inserting elements into it, searching for an element, deleting elements, and traversing the tree.

Python Program for Binary Search Tree

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

def insert(root, key):
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)
    return root

def inorder(root):
    if root:
        inorder(root.left)
        print(root.key, end=" ")
        inorder(root.right)

# Test the BST implementation
root = None
keys = [5, 3, 7, 1, 4, 6, 8]

for key in keys:
    root = insert(root, key)

print("Inorder traversal:")
inorder(root)

You can run this code on our free Online Python Compiler.

Output

To create a binary search tree, follow these steps:

1. Initialize an empty binary search tree.
2. Insert elements into the tree using the insert operation.
3. Repeat step 2 for each element you want to add.

The Python program provided in the previous section demonstrates how to create a binary search tree.

To insert an element into a binary search tree, perform the following steps:

1. If the tree is empty, create a new node with the given value and set it as the root.
2. If the tree is not empty, start from the root and compare the value with the current node’s value.
3. If the value is less than the current node’s value, move to the left child.
4. If the value is greater than the current node’s value, move to the right child.
5. Repeat steps 3 and 4 until reaching a suitable position to insert the new node.
6. Create a new node with the given value and insert it at the appropriate position.

Insertion: Python Program For Binary Sarch Tree

Here is the complete code for insertion fo an element in binary search tree.

def insert(root, key):
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)
    return root

To search for an element in a binary search tree, follow these steps:

1. Start from the root of the tree.
2. If the value of the current node matches the target value, return the node.
3. If the target value is less than the current node’s value, move to the left child.
4. If the target value is greater than the current node’s value, move to the right child.
5. Repeat steps 2-4 until finding the node with the target value or reaching a leaf node (end of the tree).
6. If the target value is not found after reaching a leaf node, the element is not present in the tree.

Searching: Python Program For Binary Search Tree

Here is the code to search an element in a binary search tree in python.

def search(root, key):
    if root is None or root.key == key:
        return root
    if key < root.key:
        return search(root.left, key)
    return search(root.right, key)

The search() function takes two parameters: root represents the current node being checked during the search, and key is the key we are searching for in the BST.

The function starts by checking if the current node root is either None or if its key matches the search key (root.key == key).

If either of these conditions is true, it means we have found the key in the BST.

In this case, the function returns the current node root.

If the search key is less than the key of the current node (key < root.key), it means the key might be present in the left subtree.

In that case, the search() function is recursively called on the left child of the current node (search(root.left, key)).

This effectively moves the search down the left subtree.

If the search key is greater than the key of the current node, it means the key might be present in the right subtree.

In this case, the search() function is recursively called on the right child of the current node (search(root.right, key)).

This moves the search down the right subtree.

If none of the conditions mentioned above are met and the key is not found in the BST, the function will return None.

The search() function is recursive, allowing it to traverse the BST until it finds the desired key or determines that it is not present in the tree.

Now lets try to search an element in a binary search tree using this.

Python Program For Binary Search Tree Searching

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

def insert(root, key):
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)
    return root

def search(root, key):
    if root is None or root.key == key:
        return root
    if key < root.key:
        return search(root.left, key)
    return search(root.right, key)

# Test the BST implementation
root = None

# Insert elements into the BST
elements = [5, 3, 7, 1, 4, 6, 8]
for element in elements:
    root = insert(root, element)

# Search for an element in the BST
search_key = 4
result = search(root, search_key)

if result is None:
    print(f"Element {search_key} not found in the BST.")
else:
    print(f"Element {search_key} found in the BST.")

You can run this code on our free Online Python Compiler.

Output

Deleting an element from a binary search tree involves three cases:

1. Deleting a leaf node: Simply remove the node from the tree.
2. Deleting a node with one child: Replace the node with its child.
3. Deleting a node with two children: Replace the node with its inorder successor (the smallest value in the right subtree) or its inorder predecessor (the largest value in the left subtree).

Deletion: Python Program For Binary Search Tree

def deleteNode(root, key):
    if root is None:
        return root

    if key < root.key:
        root.left = deleteNode(root.left, key)
    elif key > root.key:
        root.right = deleteNode(root.right, key)
    else:
        if root.left is None:
            temp = root.right
            root = None
            return temp
        elif root.right is None:
            temp = root.left
            root = None
            return temp

        temp = minValueNode(root.right)
        root.key = temp.key
        root.right = deleteNode(root.right, temp.key)

    return root

The deleteNode() function takes two parameters: root represents the current node being checked during the deletion process, and key is the key of the node to be deleted from the BST.

The function starts by checking if the current node (root) is None. If it is, it means the key is not found in the BST, so the function returns None to indicate that.

If the key is less than the key of the current node (key < root.key), it means the key to be deleted might be present in the left subtree.

In this case, we recursively call the deleteNode() function on the left child of the current node (root.left = deleteNode(root.left, key)).

This effectively moves the deletion process down the left subtree.

If the key is greater than the key of the current node (key > root.key), it means the key we wanna delete might be present in the right subtree.

In this case, we recursively call the deleteNode() function on the right child of the current node (root.right = deleteNode(root.right, key)).

This moves the deletion process down the right subtree.

If the key matches the key of the current node (key == root.key), it means we have found the node that we want to delete.

3 Cases

The function then checks three cases:

1. If the node that we want to delete has no left child (root.left is None), it means the right child should replace the node. The function sets temp as the right child, sets the current node (root) to None, and returns temp. This effectively removes the node from the BST.
2. If the node that we want to delete has no right child (root.right is None), it means the left child should replace the node. The function sets temp as the left child, sets the current node (root) to None, and returns temp. This removes the node from the BST.
3. If the node that we want to delete has both left and right children, the function finds the minimum value node in the right subtree using the minValueNode() function. It replaces the key of the current node (root.key) with the key of the minimum value node (temp.key). Then, it recursively calls the deleteNode() function on the right child of the current node to delete the duplicate key from the right subtree.

Finally, the function returns the modified root node to reflect the changes made during the deletion process.

The deleteNode() function allows for the deletion of a node with a specific key from the BST while maintaining the binary search property of the tree.

Now, let’s try to delete a node with an example program.

Deletion: Python Program For Binary Search Tree

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

def insert(root, key):
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)
    return root

def minValueNode(node):
    current = node
    while current.left is not None:
        current = current.left
    return current

def deleteNode(root, key):
    if root is None:
        return root

    if key < root.key:
        root.left = deleteNode(root.left, key)
    elif key > root.key:
        root.right = deleteNode(root.right, key)
    else:
        if root.left is None:
            temp = root.right
            root = None
            return temp
        elif root.right is None:
            temp = root.left
            root = None
            return temp

        temp = minValueNode(root.right)
        root.key = temp.key
        root.right = deleteNode(root.right, temp.key)

    return root

def inorder(root):
    if root:
        inorder(root.left)
        print(root.key, end=" ")
        inorder(root.right)

# Test the BST implementation
root = None

# Insert elements into the BST
elements = [5, 3, 7, 1, 4, 6, 8]
for element in elements:
    root = insert(root, element)
    
print("Inorder traversal before deletion:")
inorder(root)

# Delete a node from the BST
print("\nDeleting...")
delete_key = 3
root = deleteNode(root, delete_key)

# Print the inorder traversal after deletion
print("Inorder traversal after deletion:")
inorder(root)

You can run this code on our free Online Python Compiler.

Output

Traversal is the process of visiting all the nodes in a tree in a specific order. The three commonly used traversal methods for binary search trees are:

Inorder Traversal

In inorder traversal, we visit the left subtree, then the root, and finally the right subtree.

It produces the values of the tree in ascending order.

def inorderTraversal(root):
    if root is None:
        return
    inorderTraversal(root.left)
    print(root.key, end=" ")
    inorderTraversal(root.right)

Preorder Traversal

In preorder traversal, we visit the root, then the left subtree, and finally the right subtree.

def preorderTraversal(root):
    if root is None:
        return
    print(root.key, end=" ")
    preorderTraversal(root.left)
    preorderTraversal(root.right)

Postorder Traversal

In postorder traversal, we visit the left subtree, then the right subtree, and finally the root.

def postorderTraversal(root):
    if root is None:
        return
    postorderTraversal(root.left)
    postorderTraversal(root.right)
    print(root.key, end=" ")

The minimum value in a binary search tree is the leftmost node, while the maximum value is the rightmost node. To find the minimum and maximum values, follow these steps:

1. Start from the root of the tree.
2. Keep moving to the left child until reaching the leftmost node to find the minimum value.
3. Keep moving to the right child until reaching the rightmost node to find the maximum value.

Minimum Value: Python Program For Binary Search Tree

def minValue(root):
    if root is None:
        return None
    while root.left is not None:
        root = root.left
    return root.key

Maximum Value: Python Program For Binary Search Tree

def maxValue(root):
    if root is None:
        return None
    while root.right is not None:
        root = root.right
    return root.key

The height of a binary search tree is the length of the longest path from the root to a leaf node. To find the height, follow these steps:

1. If the tree is empty, the height is 0.
2. If the tree is not empty, recursively calculate the height of the left and right subtrees.
3. Return the maximum of the heights of the left and right subtrees, plus 1.

Height: Python Program For Binary Search Tree

def height(root):
    if root is None:
        return 0
    left_height = height(root.left)
    right_height = height(root.right)
    return max(left_height, right_height) + 1

Is a Binary Search Tree Balanced?

A binary search tree is considered balanced if the heights of its left and right subtrees differ by at most one.

The balancing of a binary search tree ensures efficient search, insertion, and deletion operations.

Balancing a Binary Search Tree

Balancing a binary search tree involves rearranging its nodes to ensure that the tree is balanced.

There are various algorithms for balancing binary search trees, such as AVL trees and Red-Black trees.

These algorithms maintain the balance of the tree by performing rotations and color changes.

To check if a binary tree is a binary search tree, you can use the following Python program:

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

def is_bst(root):
    return is_bst_util(root, float('-inf'), float('inf'))

def is_bst_util(node, min_value, max_value):
    if node is None:
        return True
    
    if node.value <= min_value or node.value >= max_value:
        return False
    
    return (is_bst_util(node.left, min_value, node.value) and
            is_bst_util(node.right, node.value, max_value))

This program checks if a given binary tree with nodes of integer values is a binary search tree.

It uses the concept of range validation to ensure that the values in the left subtree are less than the current node’s value, and the values in the right subtree are greater than the current node’s value.

Now, let’s test all the functions that we have discussed earlier with an example program.

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

def insert(root, key):
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)
    return root

def search(root, key):
    if root is None or root.key == key:
        return root
    if key < root.key:
        return search(root.left, key)
    return search(root.right, key)

def delete(root, key):
    if root is None:
        return root
    if key < root.key:
        root.left = delete(root.left, key)
    elif key > root.key:
        root.right = delete(root.right, key)
    else:
        if root.left is None:
            return root.right
        elif root.right is None:
            return root.left
        min_node = findMin(root.right)
        root.key = min_node.key
        root.right = delete(root.right, min_node.key)
    return root

def findMin(root):
    current = root
    while current.left is not None:
        current = current.left
    return current

def findMax(root):
    current = root
    while current.right is not None:
        current = current.right
    return current

def preorderTraversal(root):
    if root is None:
        return
    print(root.key, end=" ")
    preorderTraversal(root.left)
    preorderTraversal(root.right)

def postorderTraversal(root):
    if root is None:
        return
    postorderTraversal(root.left)
    postorderTraversal(root.right)
    print(root.key, end=" ")

# Test the BST implementation
root = None

# Insert elements into the BST
elements = [5, 3, 7, 1, 4, 6, 8]
for element in elements:
    root = insert(root, element)

# Perform search operation
search_key = 4
result = search(root, search_key)
if result is not None:
    print(f"Key {search_key} found in the BST")
else:
    print(f"Key {search_key} not found in the BST")

# Perform deletion operation
delete_key = 3
root = delete(root, delete_key)
print(f"Key {delete_key} deleted from the BST")

# Find minimum and maximum values
min_value = findMin(root).key
max_value = findMax(root).key
print(f"Minimum value in the BST: {min_value}")
print(f"Maximum value in the BST: {max_value}")

# Perform preorder traversal
print("Preorder traversal:")
preorderTraversal(root)

# Perform postorder traversal
print("\nPostorder traversal:")
postorderTraversal(root)

You can run this code on our free Online Python Compiler.

Output

Binary Search Tree Applications

Binary search trees have various applications in computer science, including:

• Database indexing
• Symbol tables
• Network routing algorithms
• File organization
• Huffman coding
• Range searches

Advantages of Binary Search Trees

Binary search trees offer several advantages:

• Efficient search, insertion, and deletion operations with an average time complexity of O(log n).
• Sorted order traversal.
• Memory efficiency, as the tree structure requires only a small amount of additional memory compared to an array or linked list.

Disadvantages of Binary Search Trees

Binary search trees have some limitations:

• If the tree is not balanced, the time complexity of operations can degrade to O(n).
• The performance depends on the tree’s structure, which can be affected by the order of element insertion.

How can I implement a binary search tree in Python?

To implement a binary search tree in Python, you can define a Node class that represents each node in the tree and a BinarySearchTree class that manages the operations on the tree.

You can refer to the Python program provided earlier in this tutorial for a complete implementation.

What are the main operations performed on a binary search tree?

The main operations performed on a binary search tree are:

• Inserting elements
• Searching for an element
• Deleting elements
• Traversing the tree

How can I insert an element into a binary search tree?

To insert an element into a binary search tree, start from the root and compare the value with the current node’s value.

If the value is less, move to the left child; if the value is greater, move to the right child.

Repeat this process until finding an appropriate position to insert the new node.

How do I search for an element in a binary search tree?

To search for an element in a binary search tree, start from the root and compare the value with the current node’s value.

If the value matches, return the node. If the value is less, move to the left child; if the value is greater, move to the right child.

Repeat this process until finding the node with the target value or reaching a leaf node.

Is it possible to delete an element from a binary search tree?

Yes, it is possible to delete an element from a binary search tree.

Deleting an element involves three cases: deleting a leaf node, deleting a node with one child, and deleting a node with two children.

The appropriate action depends on the case and the specific tree structure.

How can I balance a binary search tree?

There are various algorithms available for balancing a binary search tree, such as AVL trees and Red-Black trees.

These algorithms perform rotations and color changes to maintain the balance of the tree.

You can use these algorithms to balance a binary search tree in Python.

How to write a binary search tree program using Python?

To write a binary search tree program in Python, you can start by defining a Node class to represent each node in the tree.

Then, create a BinarySearchTree class to manage the operations on the tree, such as insertion, searching, and deletion.

Implement these operations using recursive or iterative approaches, making sure to maintain the binary search tree property where values in the left subtree are smaller than the current node, and values in the right subtree are larger.

How do you solve a binary tree in Python?

To solve a binary tree problem in Python, you need to understand the specific problem statement or task.

Depending on the problem, you may need to perform tree traversal, search for a specific value, find the height or size of the tree, or perform other operations.

Utilize appropriate algorithms and techniques, such as recursion or iterative approaches, to solve the problem efficiently.

It’s important to leverage the properties and characteristics of binary trees to devise the correct solution.

How do you create a binary search tree?

To create a binary search tree, you can start by initializing an empty tree.

Then, insert elements into the tree one by one, ensuring that the binary search tree property is maintained.

Start with the first element as the root node, and for each subsequent element, compare it with the current node’s value.

Move to the left child if the value is smaller, or move to the right child if the value is larger.

Repeat this process until you find the appropriate position to insert the new node.

Continue inserting elements until all are added to the tree.

What is a binary search tree with an example?

A binary search tree (BST) is a type of binary tree where each node has a value, and the values in the left subtree are smaller than the current node’s value, while the values in the right subtree are larger.

This property enables efficient searching, insertion, and deletion operations.

For example, consider the following binary search tree:

       8
     /   \
    3     10
   / \      \
  1   6      14
     / \     /
    4   7   13

In this example, the BST contains integer values.

The tree is constructed in such a way that for any node, the values in the left subtree are smaller, and the values in the right subtree are larger.

This property holds for all nodes in the tree.

In this tutorial, you learned how to implement a binary search tree using Python.

We covered the fundamental concepts of binary search trees, provided a Python program for creating and manipulating them, and explored various operations and traversal methods.

Binary search trees are powerful data structures that enable efficient searching, insertion, and deletion operations.

They have widespread applications in computer science and are essential to master for any aspiring programmer.

Remember to practice implementing and using binary search trees in your own projects to gain hands-on experience.

Keep exploring and expanding your knowledge to become a proficient programmer.