Python Binary Search Trees


Binary Search Tree (BST) is a special type of binary tree where:

  • Left subtree has values less than the node

  • Right subtree has values greater than the node

  • No duplicate values are allowed

This structure allows fast searching, insertion, and deletion in O(log n) time (in a balanced tree).


🔹 BST Node in Python

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

🔹 Inserting into a BST

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

Example: Create BST
root = Node(50)
insert(root, 30)
insert(root, 70)
insert(root, 20)
insert(root, 40)
insert(root, 60)
insert(root, 80)

✅ Structure:

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

🔹 Searching in a BST

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

🔹 Inorder Traversal (Sorted Output)

def inorder(root):
    if root:
        inorder(root.left)
        print(root.data, end=' ')
        inorder(root.right)

✅ Output for above tree: 20 30 40 50 60 70 80


🔹 Deleting from a BST

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

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

🔹 Use Cases of BST

  • Fast search (like a dictionary)

  • Auto-sorted data

  • Range queries

  • Indexing in databases

  • Symbol tables


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.


Go Back Top