• +91-9142290450

  • Hajipur, Bihar, 844101

☰
❮
❯

Python Binary Search Trees

← Previous Next →

A binary search tree, often called a BST, is a special type of binary tree that follows a simple ordering rule. Every node’s left child must contain a value smaller than the parent, and every node’s right child must contain a value greater than the parent. This rule applies to every node in the tree. Because of this structure, BSTs make searching, inserting and deleting values much faster than regular lists. They are widely used in databases, file systems, compilers and many algorithmic problems where quick lookups are needed.

In this chapter, you will learn what makes a BST different from a normal binary tree, how the ordering rules work, how to insert and search values, and how common operations like deletion are handled. You will also learn traversal methods and practice examples that help build a strong understanding.

What Is a Binary Search Tree?

A binary search tree is a binary tree where:

  • Left child < Parent

  • Right child > Parent

This rule helps keep values arranged in a searchable form.

Here is a simple example:

        50
       /  \
     30    70
    / \   / \
   20 40 60 80

If you search for 40, you first compare it with 50, then go left because 40 is smaller, then check 30, then go right because 40 is larger. The ordering leads you directly to the answer with fewer steps.

Why BSTs Matter

BSTs are useful because they offer:

  • Fast searching

  • Easy insertion

  • Efficient deletion

  • Better organization of data

If the tree stays balanced, most operations take very few steps, which improves overall performance.

Creating a BST Node Class in Python

You can start building a BST with a simple class:

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

Then create a function to insert a value:

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

This maintains the BST rules while adding new values.

Searching in a BST

Searching is one of the main reasons BSTs are popular. The structure guides you automatically.

def search(root, value):
    if root is None:
        return False
    if value == root.value:
        return True
    if value < root.value:
        return search(root.left, value)
    else:
        return search(root.right, value)

This function moves left or right based on comparisons, reducing the number of steps.

Inorder Traversal of a BST

Inorder traversal of a BST prints values in sorted order.

def inorder(root):
    if root:
        inorder(root.left)
        print(root.value)
        inorder(root.right)

This is helpful when you want an ordered list of values.

Building a Sample BST

root = None
values = [50, 30, 20, 40, 70, 60, 80]

for v in values:
    root = insert(root, v)

Now the tree is ready for searching and traversal.

Deleting a Node in a BST

Deletion is slightly more involved because you need to handle three cases:

Case 1: Node has no children

Just remove it.

Case 2: Node has one child

Replace the node with its child.

Case 3: Node has two children

Find the smallest value in the right subtree, swap them and delete the replacement node.

Here is a simple delete function:

def find_min(node):
    while node.left:
        node = node.left
    return node

def delete(root, value):
    if not root:
        return root

    if value < root.value:
        root.left = delete(root.left, value)
    elif value > root.value:
        root.right = delete(root.right, value)
    else:
        if not root.left:
            return root.right
        if not root.right:
            return root.left

        temp = find_min(root.right)
        root.value = temp.value
        root.right = delete(root.right, temp.value)

    return root

This keeps the tree valid after removing a node.

Level Order Traversal

You can print the BST level by level:

from collections import deque

def level_order(root):
    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.value)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

This helps visualize tree layers.

Real-Life Uses of BSTs

BSTs appear in many practical systems:

Database Indexing

Helps store and retrieve records fast.

Searching Algorithms

Repeated lookups become efficient.

File Storage

Folders and paths are often managed with tree-like structures.

Autocomplete Systems

Words stored in sorted form boost speed.

Compilers

Expression parsing and syntax trees often rely on BST logic.

BSTs act like smart directories that guide you to the right place quickly.

Practical Examples

Example 1: Insert values

root = insert(None, 10)
root = insert(root, 5)
root = insert(root, 15)

Example 2: Search for a value

print(search(root, 15))

Example 3: Print sorted order

inorder(root)

Example 4: Add more values

insert(root, 3)
insert(root, 12)

Example 5: Delete a value

delete(root, 5)

Example 6: Level order traversal

level_order(root)

Example 7: Build a BST from a list

nums = [8, 3, 10, 1, 6]
for n in nums:
    root = insert(root, n)

Example 8: Find minimum

print(find_min(root).value)

Example 9: Traverse left subtree

inorder(root.left)

Example 10: Traverse right subtree

inorder(root.right)

Summary of the Tutorial

A binary search tree follows a simple ordering rule that keeps smaller values on the left and larger values on the right. This structure makes searching, inserting and deleting values quicker than many other data structures. You learned how the BST rules work, how to insert values using recursion and how to search efficiently. You also learned common traversal techniques, how deletion works for different cases and how BSTs appear in real-world systems. With this foundation, you are now ready for more advanced tree structures like AVL trees.

Practice Questions

Q1. Write a Python program to build a Binary Search Tree (BST) with values: 10, 5, 20, 3, 7, 15, 30.

Q2. Write a Python program to search for the value 15 in the BST.

Q3. Write a Python program to perform an Inorder traversal of the BST and print the result.

Q4. Write a Python program to delete the value 5 from the BST and print the updated tree (Inorder).

Q5. Write a Python program to insert values from a list into the BST.

Q6. Write a Python program to find the smallest value in the BST.

Q7. Write a Python program to count all the leaf nodes in the BST.

Q8. Write a Python program to print all values greater than 10 in the BST.

Q9. Write a Python program to check if a binary tree is a valid BST.

Q10. Write a Python program to find and print the height of the BST.

← Previous Next →

Try a Short Quiz.

coding learning websites codepractice

No quizzes available.

Python

online coding class codepractice

Introduction to Python

Python Basics

Cotrol Structures

Data Structures

Date and Time

Functions and Module

File Handling

Python OOP

Advanced Concepts

Python DSA

Searching Algorithms

Sorting Algorithms

codepractice logo
Login
Go Back Top